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)

• David Harkness: Can the first digit in a number be 0, i.e., is every nine-digit number consisting of the digits 1 through 9 a base-10 pandigital number because you can stick 0 on the front?
• Joshua: I believe it can't start with a 0.

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

• BeetDemGuise: I just posted another answer to this question @DavidHarkness. I originally wanted to just post the idea as a comment on your answer because I liked your answer. However, my ideas would have been too jumbled in a comment. So please feel free to use any code you see fit from my answer to augment yours. +1

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)

• David Harkness: Are those digit-tests backwards? Are you sure there are nine numbers that satisfy the condition?
• BeetDemGuise: You were right, they were backwards. Thanks for the catch. And for the numbers, it must be true for the problem to be solvable. The only way a number would fit is if its 2nd triplet is divisible by 2 (i.e. must end in an even number) and if the 4th triple is divisible by 5 (i.e. must end in a 0 or a 5)
• David Harkness: My second question was referring to "If we have found all 9 numbers, stop."
• BeetDemGuise: Oops. I misread the problem statement. I thought they said that there were only 9 possible permutations. Will fix accordingly.