Speeding up Project Euler 43 - sub-string divisibility

Question

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₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

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

Project Euler 43

from itertools import permutations
from primes import primes_upto
from collections import Counter
from timeit import default_timer as timer

start = timer()
def follows_property(n):
    divisors = primes_upto(17)
    for k in range(7):
        if int(n[k:(k+3)]) % divisors[k] != 0:
            return False
    return True

ans = 0
digits = Counter(range(10))

start = timer()

for combo in permutations(range(10), 9):
    num = ''.join([str(x) for x in list(combo)])
    if follows_property(num):
        missing = int(list((digits - Counter(sorted([int(k) for k in str(num)]))).elements())[0])
        num = int(num)
        ans += int("%d%d" % (missing, num))


elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)

Answer 1

You can make a few quick improvements without altering the algorithm significantly:

• Remove one of the redundant calls to timer().

• Store the list of primes instead of calculating it for every call to follows_property.

• Convert the digits to strings in the list passed to permutations so you can simplify the calculation of num.

• Run through all permutations instead of 9-tuples and remove the Counter and missing parts.

These are minor changes, but they clean up the code a bit. I also renamed ans to sum to clarify what it holds. They also cut the running time by more than half.

from itertools import permutations
from primes import primes_upto
from collections import Counter
from timeit import default_timer as timer

divisors = primes_upto(17)

def follows_property(n):
    for k in range(7):
        if int(n[k+1:(k+4)]) % divisors[k] != 0:
            return False
    return True

sum = 0
start = timer()

for combo in permutations([str(x) for x in range(10)]):
    num = ''.join(combo)
    if follows_property(num):
        sum += int(num)

elapsed_time = (timer() - start) * 1000 # s --> ms

print("Found %d in %r ms." % (sum, elapsed_time))

Answer 2

Instead of brute-forcing 10! permutations, I'd recommend going other way around: construct the necessary ones.

You know already that the last 3 digits must form a multiple of 17 - there's just 50 or so such numbers, provided that all 3 digits shall be different. Then prepend each of them with one of remaining 7 digits (350 things to try) eliminating those which do not yield a multiple of 13. Proceed with one more digit, etc.

I hope you see the point.

Answer 3

@DavidHarkness detailed nicely what needs to be done. However, I would add a couple more checks to ensure that any unnecessary permutations aren't processed:

for combo in permutations([str(x) for x in range(10)]):
    num = ''.join(combo)

    # This ensures that the second triple of numbers is even and the 
    # fourth triplet is divisible by 5.
    if int(num[3]) % 2 == 0 and num[5] in ['0', '5']:
        if follows_property(num):
            found += 1
            sum += int(num)