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.
Programming Praxis 
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();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
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.
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
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)
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.
Thank you Matthew. Fortunately, this language, unlike Python, doesn’t lose its shit if identation fails :-)
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:])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); } } }for Matthew: Can’t you eliminate line 8 by substituting 28 for 4 on line 7 (in your first version)?
@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).
@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)@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.
A Haskell version.
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))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):