Sub-string divisibility

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₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

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

---

Idea

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

[506, 517, 528, 539, 550, 561, 572, 583, 594]

# divisible by 13
[13 * ceil((i*10) / 13) for i in [6, 17, 28, 39, 61, 72, 83, 94]]

[65, 182, 286, 390, 611, 728, 832, 949]

# divisible by 17
[17 * ceil((i % 100) * 10 / 17) for i in [286, 390, 728, 832]]

[867, 901, 289, 323]

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]

[(0, 1, 3, 4, 9),
 (0, 1, 3, 9, 4),
 (0, 1, 4, 3, 9),
 (0, 1, 4, 9, 3),
 (0, 1, 9, 3, 4),
 (0, 1, 9, 4, 3),
 (0, 3, 1, 4, 9),
 (0, 3, 1, 9, 4),
 (0, 3, 4, 1, 9),
 (0, 3, 4, 9, 1)]

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

True

def combine_digits(digits):
    return reduce(lambda n, d: n*10+d, digits, 0)

combine_digits([2, 3, 4])

234

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

16695334890