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

### April 15, 2016

Today’s exercise solves somebody’s homework problem — but not too much, since he had to write his program in Java:

Find the two smallest ten-digit pandigital numbers (numbers that contain all the digits from 0 through 9) that are divisible by the numbers 1 through 9. Then find the two largest pandigital numbers that are divisible by the numbers 1 through 9.

Your task is to solve the homework problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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[7]+a[8])%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..]))
```