Back to index.

The problem: https://projecteuler.net/problem=43

The idea here is to try all the possibilities, but with clever prunning.

Some obvious properties we must consider:

• $d_4$ must be even.
• $d_3 + d_4 + d_5 \equiv 0 \mod 3$.
• $d_6 \in \{0, 5\}$.
• $d_i d_{i+1} d_{i+2}$ is a 3-digit number divisible by 11, 13 and 17 respectively for $i = 6, 7$ and $8$. There aren't many of these. Consider the following script.

by_11 = 0
by_13 = 0
by_17 = 0

for n in range(100, 1000):
    d = n%10
    dd = (n//10)%10
    ddd = (n//100)
    if d == dd or dd == ddd or d == ddd:
        continue
    if n % 11 == 0:
        by_11 += 1
    if n % 13 == 0:
        by_13 += 1
    if n % 17 == 0:
        by_17 += 1

print(11, by_11)
print(13, by_13)
print(17, by_17)

11 64
13 50
17 39

Not just that, the five digit number $d_6 d_7 d_8 d_9 d_{10}$ has its ending part as one of the 39; its middle part as one of the 50 and its initial part as one of the 64. Our first task will be, then, to find out the possible last 5 digits based on the criteria we've gotten so far.

import itertools

def numeric_val(digits):
    n = 0
    for d in digits:
        n *= 10
        n += d
    return n

possible_endings = []

all_digits = list(range(0, 10))

for d6 in [0, 5]:
    for perm in itertools.permutations(all_digits, 4):
        if d6 in perm:
            continue
        digits = [d6]
        digits.extend(perm)
        n1 = numeric_val(digits[0:3])
        if n1 % 11 != 0:
            continue
        n2 = numeric_val(digits[1:4])
        if n2 % 13 != 0:
            continue
        n3 = numeric_val(digits[2:5])
        if n3 % 17 != 0:
            continue
        possible_endings.append(digits)

print(len(possible_endings))
print(possible_endings)

3
[[5, 2, 8, 6, 7], [5, 3, 9, 0, 1], [5, 7, 2, 8, 9]]

Success. There are very few of them. This will help with the prunning.

s = 0
all_of_them = []

for ending in possible_endings:
    digits = []
    for d in all_digits:
        if d not in ending:
            digits.append(d)
    for perm in itertools.permutations(digits, 5):        
        cand = list(perm)
        cand.extend(ending)
        n1 = numeric_val(cand[1:4])
        if n1 % 2 != 0:
            continue
        n2 = numeric_val(cand[2:5])
        if n2 % 3 != 0:
            continue
        n3 = numeric_val(cand[3:6])
        if n3 % 5 != 0:
            continue
        n4 = numeric_val(cand[4:7])
        if n4 % 7 != 0:
            continue
        n = numeric_val(cand)
        s += n
        all_of_them.append(n)

print("Sum is", s)
print("There are", len(all_of_them), "of them.")
print("They are:", all_of_them)

Sum is 16695334890
There are 6 of them.
They are: [1430952867, 4130952867, 1406357289, 1460357289, 4106357289, 4160357289]