Another quick problem post. It’s still adding variety though – I’m refusing the help of the terminal and doing this one mostly by hand (and with the help of Excel).

The problem is from Project Euler, number 43. The operating term here is pandigital number. A number if pandigital from 0 to N if it contains all the numbers from 0 to N once and only once. For example, 1234567890 is a 0-to-5 pandigital number. If we represent a pandigital 0 to 9 number by the string “abcdefghij”, we are looking for a string with such these properties:

• 2 divides bcd
• 3 divides cde
• 5 divides def
• 7 divides efg
• 11 divides fgh
• 13 divides ghi
• 17 divides hij

So, starting with the second digit (b), consecutive groups of 3 digits are divisible by consecutive primes. The solution to this problem is the sum to all such 0-to-9 pandigital numbers.

It’s probably not unreasonable to have a program go through permutations of 1234567890, of which there are 10! = 3628000, and perform these tests, but this is definitely doable by hand, which I will attempt. To do this, we will use basic divisibility rules to narrow our search space, and remember that a number can only be used once.

First, if 5 divides “def”, then f can only be a 0 or 5. However, if f = 0, then “fgh” = “0gh” is only divisible by 11 if g = h. To see why, look at the numbers divisible by 11 under 100: 011, 022, 033,… Because they contain repeated digits, 0 is out as an option for f, so f is decidedly 5.

Next, we go back to “def”. There are only a handful of 3-digit numbers divisible by 7 that have the middle digit as 5. I created a multiplication table in Excel and picked out all such numbers: 056, 154, 259, 350, 357, 651, 658, 756, 854, 952. Immediately we see that our search space is already reduced considerably.

We move to the right in our string because there are fewer numbers divisible by 11, 13, and 17 than numbers divisible by 2 and 3. Again, I had to consult a multiplication table, but for 11. For each number in the previous list, we look at two rightmost digits, and see if they appear in the multiplication table for 11 as the first two digits. For example, for 056, “561” appears in the table, so it’s a possible candidate, however, “54g” doesn’t appear in the table for any value of g. Progressing this way, we find possible values for “defg”: 0561, 2954, 3506, 3572, 6517, 6583, 7561.

The values for i and j are found the exact same way. By consulting a multiplication table for 13 and 17, we look at the two rightmost numbers in the previous list, and see if they appear as the first two digits of any number. Our list is considerably shorter by the end of this. Possible candidates for efghij: 357289, 952867.

With that, we are done with the six rightmost digits. To move left, we consider candidates for d. Note that since 6 digits have been decided, d can only take on four values, namely {0, 1, 4, 6} for 357289, and {0, 1, 3, 4} for 952867. We can eliminate a few more options with some observations: “bcd” is divisible by 2, so that bcd is a even number, which means it can only be one of 0, 2, 4, 6, or 8. So in each set of four candidates, we eliminate the odd numbers. Our list is now: 0357289, 4357289, 6357289, 0952867, 4952867.

The logic for choosing “c” will depend on a little-known rule for divisibility by 3: a number is divisible by 3 if the sum of all digits results in a number divisible by 3. Then for each candidate in the previous list, we consider numbers that could be formed by the 3 remaining unused numbers, and look at the first three digits to see if they pass the test. For example, 0357289 leaves {1, 4, 6} unused. Of these, concatenated with 03, only 603 is divisible by 3. So we get 60357289 out of this. Note that some candidates above don’t have any unused number that could be used to pass this test. Our list is now: 60357289, 06357289, 30952867.

Finally, note that each candidate in the previous list unconditionally passes the test for bcd, that is, bcd divisible by 2. To see why, regardless of what b is, “b60”, “b06”, and “b30” will always be divisible by 2. After choosing b, we have used nine of ten possible digits, so a is also decided.

Our final list and the sum is:

1460357289

4160357289

1406357289

4106357289

1430952867

4130952867

_______________

16695334890

More posts will probably be more like this and the last for the near future, since I’m getting ready for a programming competition and Microsoft Puzzle Challenge, but I may put up what I’ve been working on for my ECE4180 – Embedded Systems class.