Sub-string Divisibility¶

If you really wanted to, you could work this out with pen and paper using divisibility rules. Alternatively, it's easy to brute force. First we write a function to test for the given property.

In [1]:
def is_substring_divisible(digits):
    for idx, divisor in enumerate((2, 3, 5, 7, 11, 13, 17), start=1):
        x, y, z = digits[idx:idx+3]
        n = 100*x + 10*y + z
        if n % divisor != 0:
            return False
    
    return True

Then we test every permutation of 0 through 9. There's $10! = 3628800$ such permutations, which may seem like a lot, and you could apply some logic to reduce the search space some (e.g. $d_4$ must be 0, 2, 4, 6, or 8), but the test runs relatively quickly for each permutation as-is.

In [2]:
from itertools import permutations

numbers = set()
for digits in permutations((0,1,2,3,4,5,6,7,8,9)):
    if is_substring_divisible(digits):
        n = sum(10^k * digit for (k, digit) in enumerate(reversed(digits)))
        numbers.add(n)
        
numbers
Out[2]:
{1406357289, 1430952867, 1460357289, 4106357289, 4130952867, 4160357289}

Turns out there's only six of these numbers.

In [3]:
sum(numbers)
Out[3]:
16695334890

Relevant sequences¶

  • Pandigital numbers: A050278

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.