Project Euler Problem 43: SubString 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 substring 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