Project Euler Solution 43: Sub-string divisibility

And today from the Project Euler Series we have Problem 43: 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_1$ be the 1st digit, $d_2$ be the 2nd digit, and so on. In this way, we note the following:

d_2 d_3 d_4=406 is divisible by 2 d_3 d_4 d_5=063 is divisible by 3 d_4 d_5 d_6=635 is divisible by 5 d_5 d_6 d_7=357 is divisible by 7 d_6 d_7 d_8=572 is divisible by 11 d_7 d_8 d_9=728 is divisible by 13 d_8 d_9 d_{10}=289 is divisible by 17

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

As one can already see in the example, there are substrings which start with 0. This will make int interpret it as an octal digit, therefore we need a special function which can take care of that.

def int_with_zero(number: str) -> int:
    while number[0] == "0":
        number = number[1:]
    return int(number)

Then we can implement this property. We take various beginnings and match them up with the prime numbers. Then we check whether the substring is divisible by that prime number. Only if everything passes, we return true.

def has_property(digits: int) -> bool:
    for prime, begin in zip(prime_generator(), range(1, len(digits) - 2)):
        sub_digits = digits[begin : begin + 3]
        sub = int_with_zero("".join(sub_digits))
        if sub % prime > 0:
            return False
    else:
        return True

A little test makes sure that it works for the example.

def test_has_property() -> None:
    assert has_property("1406357289")

As this is the only test, one could always return true and it would pass the test. But as I have written the function beforehand, I think that this is okay.

Then we just iterate through all the permutations that can be formed and checked whether the numbers have the property that we want to look at.

def solution_all_permutations() -> int:
    results = []
    for digits in itertools.permutations(map(str, range(10))):
        if digits[0] == 0:
            continue
        if has_property(digits):
            number = int("".join(digits))
            results.append(number)
    print(sorted(results))
    return sum(results)

This works, but it takes 4.7 s to finish.

A more clever way

We can do better because we already know that there is an overlap in the digits and that each part has to be divisible by the relevant prime. Therefore we can write a function which takes a number (as string) that is divisible by 17 already. We have a set of the remaining digits. It will tack on all remaining digits to the front and verify whether the first three digits are divisible by the relevant prime number. If so, it will yield the number.

def another_digit(number: str, digits_available: set[str]) -> int:
    primes = [2, 3, 5, 7, 11, 13, 17]
    for digit in digits_available:
        candidate = digit + number
        if len(candidate) == 10:
            yield int_with_zero(candidate)
        else:
            relevant_prime = primes[-(len(number) - 1)]
            if int_with_zero(candidate[:3]) % relevant_prime == 0:
                yield from another_digit(candidate, digits_available - {digit})

And then we can start this with all three digit numbers that are multiples of 17.

def solution_selective_permutations() -> int:
    results = []
    for m in range(999 // 17 + 1):
        number = f"{17 * m:03d}"
        if len(set(number)) != 3:
            continue
        digits_available = set("0123456789") - set(number)
        results.extend(another_digit(number, digits_available))
    return sum(results)

This creates much fewer numbers and therefore finishes in just 405 µs. That is again an improvement by a factor of 10,000, which is amazing. If one had started with iterating all ten digit numbers and checking for the pandigital property, it would have taken forever.