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

• 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? May 16 '14 at 22:01
• I believe it can't start with a 0. May 17 '14 at 14:38

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

• 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 May 16 '14 at 23:26

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.

@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) % 2 == 0 and num in ['0', '5']:
if follows_property(num):
found += 1
sum += int(num)

• Are those digit-tests backwards? Are you sure there are nine numbers that satisfy the condition? May 16 '14 at 23:31
• 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) May 16 '14 at 23:37
• My second question was referring to "If we have found all 9 numbers, stop." May 16 '14 at 23:48
• Oops. I misread the problem statement. I thought they said that there were only 9 possible permutations. Will fix accordingly. May 16 '14 at 23:49