## Ten-Digit Pandigital Numbers Divisible By 1 Through 9

### April 15, 2016

This is easy. We begin by noting that the least common multiple of the digits 1 through 9 is 2520, and that the smallest ten-digit multiple of 2520 is 1000001520. Then we find all the ten-digit pandigital multiples of 2520 with a list comprehension:

```(define xs
(list-of n
(n range 1000001520 10000000000 2520)
(= (undigits (sort < (digits n))) 123456789)))```

There are about 3.5 million ten-digit multiples of 2520, so it only takes a few seconds to generate them all and test them for pandigital-ness (is that a word?). Now we can answer questions about them:

```> (length xs)
11460
> (car xs)
1234759680
1234857960
9876134520
> (car (reverse xs))
9876351240```

Having a good Standard Prelude available makes this exercise trivial; our solution was easy to write, is easy to read, and works relatively quickly. We could make it much faster by calculating only the two smallest and two largest members of the set as the question requires, but it’s more fun to see the entire solution set, and doesn’t take too long. You can run the program at http://programmingpraxis.codepad.org/iNjfmAsg.

Pages: 1 2

### 15 Responses to “Ten-Digit Pandigital Numbers Divisible By 1 Through 9”

1. Simple in perl as well…

```print join "\n", @{[ grep { '0123456789' eq join q(), sort split m{}, \$_ } map { \$_ * 2_520 } 390_000 .. 4_000_000 ]}[0,1,-2,-1],q();
```
2. Dr. Z said

function is_divisible_by_all_digits(x::Int64)
for z = 2:9
if x % z != 0
return false
end
end

return true
end

function find_all_pandigitals()
X = collect(permutations([1,2,3,4,5,6,7,8,9,0]))[1:end-362880]
N = length(X)
y = Array(Int64, N)

for i = 1:N
x = X[i]
y[i] = x[end]

for j = 1:9
y[i] += x[end-j] * 10^j
end
end

return y
end

function main()
Z = Array(Int64, 2, 2)
p = find_all_pandigitals()
# N = length(p)
y = []

for x in p
if is_divisible_by_all_digits(x)
push!(y, x)
end
end

M, ind = findmin(y)
Z[1,1] = M
y[ind] = 9999999999999999999
M = minimum(y)
Z[1,2] = M
y[ind] = 0
M, ind = findmax(y)
y[ind] = 0
Z[2,1] = M
M = maximum(y)
Z[2,2] = M
return Z
end

Memory used: 1.158 GB
Execution time: a bit less than 3.5 sec

3. matthew said

This should get them high marks if the relevant library functions exist in Java. Needs C++14 (for auto lambda parameters).

```#include <iostream>
#include <algorithm>
int main() {
int a[] = {1,2,3,4,5,6,7,8,9};
int b[] = {2,3,1,5,4,6,2,3,1};
while(std::next_permutation(a,a+9)) {
if ((10*a+a)%4) continue;
if (std::inner_product(a,a+9,b,0)%7) continue;
std::for_each(a,a+9,[](auto d){ std::cout << d; });
std::cout << "0" << "\n";
}
}
```

Like the suggested solution, generates all 11460 solutions (in 0.018 seconds apparently). Note that there is no conversion to or from strings.

4. matthew said

Perhaps I should explain that a bit: as noted, we want multiples of 9*8*7*5 = 2520 = 252 * 10, so just generate permutations of 1-9 and put a 0 on the end to get the 10 factor. All pandigital numbers are divisible by 9 (sum of digits is 45) so don’t need to check for that. Just leaves 4 and 7: 4 is easy and the inner product is a wacky test for divisibility by 7 I got from https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml

5. Dr. Z said

That changes things. If that’s the case, my script can accomplish the task in a bit more than 1.3sec (same memory usage though)

6. matthew said

Have fun…

You might want to have a look at: https://en.support.wordpress.com/code/posting-source-code/ – if your language (Julia?) isn’t there then ‘language=”text”‘ will preserve indentation as well.

7. Dr. Z said

Thank you Matthew. Fortunately, this language, unlike Python, doesn’t lose its shit if identation fails :-)

8. Paul said

Generate all permutations of 1-9 and check if the numbers are divisible bu 252.

```for p in permutations("123456789"):
i = int("".join(p))
if not i % 252:
res.append(i * 10)
print(res[:2])
print(res[-2:])
```
9. matthew said

Can’t resist some micro-optimization: a hand-rolled integer conversion function (with an explicit length, so we can use it with strings without a NUL terminator) is nice & quick (notice that all those auto’s mean that the only thing specifying the return type of toint is the UL suffix on the 0 initial value – we can do all this with ints, but only just). Runtime now about 8ms.

```#include <stdio.h>
#include <algorithm>
int main() {
char a[] = "1234567890\n";
auto toint = [](auto p,auto k) {
auto g = [](auto n, auto d){ return 10*n+d-'0'; };
return std::accumulate(p,p+k,0UL,g);
};
while(std::next_permutation(a,a+9)) {
if (toint(a+7,2)%4 == 0 && toint(a,9)%7 == 0) {
fwrite(a,1,sizeof(a)-1,stdout);
}
}
}
```
10. Ernie said

for Matthew: Can’t you eliminate line 8 by substituting 28 for 4 on line 7 (in your first version)?

11. matthew said

@Ernie: Thanks for asking (and glad someone is paying attention) – I could indeed do that, but it would make the program slower – the first check is much faster than the second and eliminates approx 75% of the cases (same for the first clause on line 10 of the second version).

12. Paul said

@matthew. This Python code runs well below 1 ms. It only calculates the requested 4 numbers. Of course, in C you should be able to do this a lot faster.

```asc =  "123456789"
desc = "987654321"

perms_asc = (int("".join(p)) for p in permutations(asc))
perms_desc = (int("".join(p)) for p in permutations(desc))
ans_asc = (i*10 for i in perms_asc if i % 252 == 0)
ans_desc = (i*10 for i in perms_desc if i % 252 == 0)
res_asc = list(islice(ans_asc, 2))
res_desc = list(islice(ans_desc, 2))

print(res_asc)
print(res_desc)
```
13. matthew said

@Paul: Well, I would hope just generating 4 solutions rather than all 11460 would be faster. Good point though: C++ doesn’t have a nice compact way of doing on-demand data streams like Python-style generators or Haskell-style lazy lists, though you can do some fun things with iterators & no doubt there is something in Boost.

14. Globules said

```import Data.Bits
import Data.Word

-- Candidate numbers in increasing and decreasing order.
--
-- Base is the smallest number divisible by 1 through 9.  All candidates will
-- be multiples of this value.
--
-- Low and high will constrain our search, being the smallest and largest 10
-- digit numbers that are multiples of base.
candidates :: ([Int], [Int])
candidates = let base = 2*2*2 * 3*3 * 5 * 7
low  = quot 1023456789 base * base
high = quot 9876543210 base * base
in ([low, low + base .. high], [high, high - base .. low])

isPandigital :: Int -> Bool
isPandigital = go (0x03ff :: Word16)
where go set 0 = set == 0
go set n = let (q, r) = n `quotRem` 10
in go (set `clearBit` r) q

main :: IO ()
main = do
let (incr, decr) = candidates
putStrLn \$ "Smallest: " ++ show (take 2 (filter isPandigital incr))
putStrLn \$ " Largest: " ++ show (take 2 (filter isPandigital decr))
```
```\$ ./pandig
Smallest: [1234759680,1234857960]
Largest: [9876351240,9876134520]
```
15. matthew said

I just reallized that my reply to @Ernie up above isn’t quite right – the check for divisibility by 4 is essential in the first solution as the inner-product test is specifically just for divisibility by 7; it’s non-essential in the second solution though.

Anyway, here’s another Haskell solution: directly generate a list of pandigital numbers and take the intersection with multiples of 252 (with a multiplication by 10 at the end as before):

```import Data.List
import Data.List.Ordered

pandigital n [] = [n]
pandigital n s = concatMap (\a->pandigital (10*n+a) (delete a s)) s

main = print \$ take 2 (map (*10) (isect (pandigital 0 [1..9]) [0,252..]))
```