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 > (cadr xs) 1234857960 > (cadr (reverse xs)) 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.
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):