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

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=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.


In [1]:
from math import ceil
from itertools import permutations
from functools import reduce
In [2]:
# divisible by 11
[11 * i for i in range(ceil(500 / 11), ceil(600 / 11))]
Out[2]:
[506, 517, 528, 539, 550, 561, 572, 583, 594]
In [3]:
# divisible by 13
[13 * ceil((i*10) / 13) for i in [6, 17, 28, 39, 61, 72, 83, 94]]
Out[3]:
[65, 182, 286, 390, 611, 728, 832, 949]
In [4]:
# divisible by 17
[17 * ceil((i % 100) * 10 / 17) for i in [286, 390, 728, 832]]
Out[4]:
[867, 901, 289, 323]
In [5]:
def get_remain_digits_permuations(last_five_digits):
    remain = set(range(10)) - set(map(int, str(last_five_digits)))
    return permutations(remain)
In [6]:
list(get_remain_digits_permuations(52867))[:10]
Out[6]:
[(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)]
In [7]:
def is_candidate(permutation):
    # divisible by 2 and 3
    return permutation[3] % 2 == 0 and sum(permutation[2:5]) % 3 == 0
In [8]:
is_candidate((1,4,0,6,3))
Out[8]:
True
In [9]:
def combine_digits(digits):
    return reduce(lambda n, d: n*10+d, digits, 0)
In [10]:
combine_digits([2, 3, 4])
Out[10]:
234
In [11]:
def is_substring_divisible(candidate):
    # divisible by 7
    return combine_digits(candidate[4:7]) % 7 == 0
In [12]:
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
In [13]:
solve()
Out[13]:
16695334890