## 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.

Advertisements

Simple in perl as well…

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).

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.

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.

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.

@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.

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):