Project Euler Solution #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 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.

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;
}