Project Euler Problem 43: Sub-String Divisibility

The source code for this problem can be found here.

Problem Statement

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 \(1^{st}\) digit, \(d_2\) be the \(2^{nd}\) 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.

Solution Discussion

Nothing sophisticated here. Simply iterate through all \(0\) through \(9\) pandigital numbers and test for the required divisibility properties. Accumulate the sum of qualifying candidate pandigital numbers.

Solution Implementation

from itertools import permutations

from lib.digital import digits_to_num


def solve():
    """ Compute the answer to Project Euler's problem #43 """

    divisors = [2, 3, 5, 7, 11, 13, 17]

    answer = 0
    for digits in permutations(range(10)):
        for i, divisor in enumerate(divisors):
            z = sum([100 * digits[i + 1] + 10 * digits[i + 2] + digits[i + 3]])
            if z % divisor != 0:
                break  # one of the divisibility constraints doesn't hold, skip over this pandigital
        else:
            answer += digits_to_num(list(digits))
    return answer


expected_answer = 16695334890

solutions.problem43.solve()

Compute the answer to Project Euler’s problem #43