Project Euler 491 - Double pandigital number divisible by 11

Official link:

Thought Process

The problem is based around divisibility by 11, so a good start would be Divisibility rules for 11, the one I used is the alternating sum of digits, and the reason is because we can cut down on a lot of computation.

The sum of all digits is 90, this means that if we have the sum of all odd digits, lets say O then the sum of all even digits is E = 90 - O.

Therefore we have that if a number is divisible by 11 then O - E = O - (90 - O) = 2O - 90 is also divisible by 11.

Because of this we no longer care about the position of the digits, if we are given a tuple say (1,2,3,4,4,5,6,6,7,7) which represents the digits on odd positions then we immediately know the remaining digits (0,0,1,2,3,5,8,8,9,9) lie on the even positions.

Given the above we have O = 45 => 2O-90 = 0 which is divisible by 11. We so know that any double pandigital with the respective even and odd place choices will be divisible by 11, so how many are there?

Well 0 cannot be in the first slot, but this is no problem because 0 is not on an odd position so it cannot take the first spot, so we simply need the number of combinations of (1,2,3,4,4,5,6,6,7,7), this is simply 10!/(2!*2!*2!) because 4,6,7 appear twice, and the remaining even position digits are exactly the same with 10!/(2!*2!*2!) orderings, so in total we have (10!/(2!*2!*2!))^2 number of double pandigital's with these exact numbers.

All that is left to do is generate all the possible ordering for odd positioned numbers (this is made easy with itertools.combinations, however it is quite a challenge to make your own function that does this, I recommend trying it), and to account for if there is a 0 in the odd positioned numbers, because if there is you will have less possible choices.

  1. If there is no 0

    • Then we do the above

  2. If there is 1, 0

    • Then when finding the number of ordering's remember a 0 cannot be in the first position so you have 9 choices for first position and 9! for rest (Don't forget to divide by 2 for duplicate numbers)

  3. If there is 2, 0's

    • 8 choices for first position and again 9! for rest (Don't forget to divide by 2 for duplicate numbers)

Interactive Code

No interactive code for this problem, my code is given below