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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
Find the sum of all 0 to 9 pandigital numbers with this property.
At first glance, we get: $ \begin{cases} d_4 \bmod 2 = 0 \\ (d_3+d_4+d_5) \bmod 3 = 0 \\ d_6 = 0 \ or \ 5 \end{cases} $
if $d_6=0$, then $d_7, d_8$ must be same if "$d_6d_7d_8$ is divisible by 11", which violates the rule of pandigital.
So, $ d_6 =5 $, this is the key to this problem.
Then start with "$d_6d_7d_8$ is divisible by 11", we can get $d_6d_7d_8$ must be in [506, 517, 528, 539, 561, 572, 583, 594]
Then start with "$d_7d_8d_9$ is divisible by 13", we can get $d_7d_8d_9$ must be in [286, 390, 728, 832]
Then start with "$d_8d_9d_{10}$ is divisible by 17", we can get $d_8d_9d_{10}$ must be in [867, 901, 289]
Chain the above three conclusions, we get $d_6d_7d_8d_9d_{10}$ must be in [52867, 53901, 57289]
Together with the first observation, we can reduce search space quite a lot.
from math import ceil
from itertools import permutations
from functools import reduce
# divisible by 11
[11 * i for i in range(ceil(500 / 11), ceil(600 / 11))]
# divisible by 13
[13 * ceil((i*10) / 13) for i in [6, 17, 28, 39, 61, 72, 83, 94]]
# divisible by 17
[17 * ceil((i % 100) * 10 / 17) for i in [286, 390, 728, 832]]
def get_remain_digits_permuations(last_five_digits):
remain = set(range(10)) - set(map(int, str(last_five_digits)))
return permutations(remain)
list(get_remain_digits_permuations(52867))[:10]
def is_candidate(permutation):
# divisible by 2 and 3
return permutation[3] % 2 == 0 and sum(permutation[2:5]) % 3 == 0
is_candidate((1,4,0,6,3))
def combine_digits(digits):
return reduce(lambda n, d: n*10+d, digits, 0)
combine_digits([2, 3, 4])
def is_substring_divisible(candidate):
# divisible by 7
return combine_digits(candidate[4:7]) % 7 == 0
def solve():
s = 0
for last_five_digits in [52867, 53901, 57289]:
for candidate in filter(is_candidate, get_remain_digits_permuations(last_five_digits)):
if is_substring_divisible(candidate + tuple(map(int, str(last_five_digits)))):
s += (combine_digits(candidate) * int(1e5) + last_five_digits)
return s
solve()