## Question

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let $d_1$ be the $1^{st}$ digit, $d_2$ be the $2^{nd}$ digit, and so on. In this way, we note the following:

\displaystyle \begin{aligned} d_2d_3d_4 & =406 \text{ is divisible by 2} \\ d_3d_4d_5 & =063 \text{ is divisible by 3} \\ d_4d_5d_6 & =635 \text{ is divisible by 5} \\ d_5d_6d_7 & =357 \text{ is divisible by 7} \\ d_6d_7d_8 & =572 \text{ is divisible by 11} \\ d_7d_8d_9 & =728 \text{ is divisible by 13} \\ d_8d_9d_{10} & =289 \text{ is divisible by 17} \end{aligned}

Find the sum of all 0 to 9 pandigital numbers with this property.

import Data.List (nub)

expand :: Int -> String -> [String]
expand x "" = [s | n <- [100..999], n rem x == 0, let s = show n, s == nub s]
expand x s = [c:s | c <- ['0'..'9'], c notElem s, (read (c:take 2 s)) rem x == 0]

candidates :: [String]
candidates = inner [17, 13, 11, 7, 5, 3, 2, 1] [""] where
inner [] acc = acc
inner (x:xs) acc = inner xs $concatMap (expand x) acc main :: IO () main = print$ sum $map read candidates $ ghc -O2 -o pandigital-substrings pandigital-substrings.hs
$time ./pandigital-substrings real 0m0.004s user 0m0.000s sys 0m0.000s ## Python #!/usr/bin/env python from itertools import * def has_property(digits): primes = [1,2,3,5,7,11,13,17] for i in range(1, len(digits)-2): if not int(''.join(digits[i:i+3])) % primes[i] == 0: return False return True def convert_list_to_int(l): return int(''.join(str(i) for i in l)) def main(): pandigitals = permutations((str(i) for i in range(10))) print(sum(convert_list_to_int(p) for p in pandigitals if has_property(p))) if __name__ == "__main__": main() $ time python3 pandigital-substrings.py
real   0m7.946s
user   0m7.888s
sys    0m0.004s

## Ruby

#!/usr/bin/env ruby
primes = [1,2,3,5,7,11,13,17]
puts ('0'..'9').to_a.permutation.select { |digits|
(1..7).all? { |i|
digits[i..i+2].join('').to_i % primes[i] == 0
}
}.map { |digits| digits.join('').to_i }.reduce(:+)
\$ time ruby pandigital-substrings.rb
real   0m8.062s
user   0m7.964s
sys    0m0.012s

Questions? Comments? Send me an email: z@chdenton.com