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 --&gt; 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 --&gt; ms

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