Project Euler 43 Solution: Sub-string divisibility

Problem 43

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.

Solution

This problem can easily be solved by generating all $$10!$$ combinations and check the divisibility properties. With the fast algorithm we derived for Problem 24, this would solve the problem quickly. But we can analyze the properties to shrink the search space as much as we can.

$$d_2d_3d_4$$ must be divisible by two, from which follows that $$d_4$$ must be even. $$d_3d_4d_5$$ must be divisible by 3 from which follows that $$d_3+d_4+d_5$$ is divisible by 3. $$d_4d_5d_6$$ must be divisible by 5 from which follows that $$d_6$$ is either 0 or 5.

We know that $$d_6d_7d_8$$ must be divisible by 11 and we also know that $$d_6$$ is either 0 or 5. If it is 0, the numbers must be of the form $$\{011, 022, 033, ... 099\}$$, which are not valid. It follows that $$d_6$$ must be 5 and all possible numbers divisible by 11 that begin with 5 are $$\{506, 517, 528, 539, 561, 572, 583, 594\}$$. Since the next block $$d_7d_8d_9$$ must be divisible by 13, we further reduce the 8 possibilities down to 4, $$\{5286, 5390, 5728, 5832\}$$, for $$d_6d_7d_8d_9$$.

$$d_8d_9d_{10}$$ must be divisible by 17. Based on the previous block of possible solutions, we can conclude that $$d_6d_7d_8d_9d_{10}$$ can only be $$\{52867, 53901, 57289\}$$, which are all possible endings of the pandigital number. Going into the other direction and checking what three digit numbers $$d_5d_6d_7$$ are divisible by 7 where $$d_6d_7$$ is either 52, 53 or 57 can be brute forced quickly: $$\{952, 357\}$$. Concatenating to $$d_5d_6d_7d_8d_9d_{10}$$ leaves two possible solutions, $$\{952867, 357289\}$$.

We know that $$d_4$$ must be even, $$d_5$$ is either 3 or 9 and that $$d_3+d_4+d_5$$ must be divisible by 3. All possible combinations are {063, 069, 123, 129, 183, 189, 243, 249, 309, 369, 423, 429, 483, 489, 543, 549, 603, 609, 723, 729, 783, 789, 843, 849, 903, 963}. That's a lot, but removing the ones that are impossible when concatenated to the rest only leaves $$\{30952867, 60357289, 06357289\}$$. We don't have any further restrictions for $$d_1$$ and $$d_2$$ and since the only two digits that are not used yet are 1 and 4, we can use both, leading to the following solution:

function solution() {
return 1430952867 + 1460357289 + 1406357289 + 4130952867 + 4160357289 + 4106357289;
}

« Back to problem overview