Project Euler 43

Problem 43 of project euler is a strange problem, at least in my eyes. First off it starts talking about pandigital numbers. Pan, of course, means across so we can think of it as across digit numbers, which they define as a number that contains every digit (0-9) once and only once. Given that there are 10 digits here and any permutation of them would be a pandigital number there are 10! (thats 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) different combinations, about 3 million.

So that is the size of our search space, not incredibly large, but the problem gets trickier. They only want pandigitals which small portions of are divisible by prime numbers. I believe that their example makes it clear exactly what they want.

Take the pandigital 1406357289. Then lets look at a small section of it 3 digits at a time:

• 1406357289 is divisible by 2
• 1406357289 is divisible by 3
• 1406357289 is divisible by 5
• 1406357289 is divisible by 7
• 1406357289 is divisible by 11
• 1406357289 is divisible by 13
• 1406357289 is divisible by 17

So its clear that this will yield a great deal fewer numbers than 3 million.

So as usual I coded a naive approach to see how it performs and to make sure I can answer the question. I implemented a function that takes in a 10 digit number and checks to see if the digits in index 2 through 4 are divisible by 2, then the digits 3 through 5 are divisible by 3 then.... etc
. Then I simply generated every single permutation of the digits 0-9 and threw away any that did not pass the function, from there you can simply sum up all of the remaining ones and you have your answer.
Hopefully the python makes this clear.

from itertools import permutations

def wtf_problem_43(number):
    primes = [2,3,5,7,11,13,17]
    for i in range(len(primes)):
        if int(number[1 + i:4 + i])%primes[i] != 0:
            return False
    return True

print sum(map(int,filter(wtf_problem_43,map(''.join,permutations("1234568790")))))

This code does indeed work, but it takes 47.6 seconds to execute. Surely we can do better!


First off there is no need to generate every permutation of the digits 0-9. Surely we can cut a large amount of those out of the search space very quickly. Right off the bat what we could do is simply focus on generating only a 3 digit chunk that is divisible by its relevant prime number. It would be like instead of generating 1406357289 we only generate 406, because it is divisible by 2. Then we would only need to try every remaining number (1,2,3,5,7,8,9) in the last slot of 06_ and see if it is divisible by 3.


This turns the problem into a constraint satisfaction problem (sudoku is a famous CSP) and a nice trick for solving these very quickly is to first make choices where it cuts out the large number of potentials. For instance there are 360 diffent ways to start if we start with the ones divisible by 2, but if we start backwards, with different ways to make numbers that are divisible by 17 we only have 44 of them.

So I created a recursive generator that will yield all of the relevant numbers.

This code is significantly more complex, I left some comments, but recursive generators are a little hard to understand. I personally recommend adding the decorator that prints out the arguments that a function gets when it is called. (add this by putting @dump_args before the function declaration).

from itertools import permutations

def generator(divisors,remaining, previous=""):
    if divisors: #if divisors is empty, then only one digit remains
        if previous == "": #This iteration is the starting iteration, it simply recalls its self with every permutation of the last two digits
            for permutation in permutations(remaining,2):
                permutation = ''.join(permutation) #('1','2') -> "12"
                for i in generator(divisors,remaining.translate(None,permutation),permutation):
     #translate strips the used digits, ensuring pandigitality
                    yield i + permutation
        else:
            for permutation in permutations(remaining,1): #unnecessarily complex, I just wanted it to look consistent
                permutation = ''.join(permutation) + previous[:2]
                if int(permutation)%divisors[0] == 0:#
                    for i in generator(divisors[1:],remaining.translate(None,permutation),permutation):
                        yield i + permutation[0]
    else:
        yield remaining

            
print sum(map(int,generator([17,13,11,7,5,3,2],"1234568790")))

Even though this code could still be speed up it solves the problem in just 0.008 seconds! Again, if after looking at the code with the dump_args decorator you still do not understand it, please leave me a comment.