Speeding up Project Euler 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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way,
we note the following:

• d2d3d4=406 is divisible by 2

• d3d4d5=063 is divisible by 3

• d4d5d6=635 is divisible by 5

• d5d6d7=357 is divisible by 7

• d6d7d8=572 is divisible by 11

• d7d8d9=728 is divisible by 13

• d8d9d10=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)

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))

StackExchange Code Review Q#50965, answer score: 5