October 30, 2016

Horse 2184 - 381,654,729

Matt Parker, the stand-up mathematician¹, in his book "Things to Make and Do in the Fourth Dimension"², talks of a maths problem which he asked someone to give him so  that he'd have something to do in the dentist's chair. It goes something like this:

Arrange the digits 1 to 9 in order so that the first two digits form a multiple of 2, the first three digits form a multiple of 3, the first four digits form a multiple of 4 etc. and finally the entire number is a multiple of 9.

The problem asks someone to generate a polydivisible number, which is a number abcdef... etc. where:
- Its first digit a is not 0.
- The number formed by its first two digits ab is a multiple of 2.
- The number formed by its first three digits abc is a multiple of 3.
- The number formed by its first four digits abcd is a multiple of 4.
- et cetera, et cetera, et cetera³

I work as an accountant; this means that as a far as mathematics goes, I am the absolute scum of the world. My whole job is virtually nothing more than the four basic operations (addition, subtraction, multiplication, and division) and doing the equivalent of sudoku all day long by fitting numbers into fancy grids called tax returns.
Even so, doing this should be a piece of cake. In fact, it should be possible to go through all of the polydivisible numbers for all of the conditions such that:

Arrange the digits 1 to n in order so that the first two digits form a multiple of 2, the first three digits form a multiple of 3, the first four digits form a multiple of 4 etc. and finally the entire number is a multiple of n.

... for all of the digits in base-10,

1 digit.
1 - is one and all alone and ever more shall be so. All integers are divisible by 1 by definition; since we only have 1 digit, there is not choice.

2 digits.
12 - All even numbers are divisible by 2. Since the other way of arranging these digits is odd, that is wrong.

3 digits.
123 - All numbers which are divisible by 3, have the result that if you sum the digits, then that result is also divisible by 3. We just happen to be lucky that 1+2+3=6 and 6 is divisible by 3. Also, 2 must appear in the middle to satisfy first two digits forming a multiple of 2. This is important as it also says that for every even value of n, these positions must also be occupied by even digits.
321 - See above.

4 digits.
Problem.
All numbers which are divisible by 4, happen to have the last two numbers as a multiple of 4. 4 cannot appear in the last position because 14 and 34 are not divisible by 4. This means that 12 and 32 are the only possible candidates.
Problem.
If 12 and 32 are the last two digits, then 4 must appear in position 2. That means that the three digits which are available for those first three positions are 1, 3 and 4 but 1+3+4=8 and 8 is not divisible by 3.
Therefore there are no 4 digit solutions.

5 digits.
Problem.
All numbers divisible by 5 either end in 5 or 0. This will be useful for all subsequent problems. However, this means that 5 must appear in position 5; since 5 is in position 5 then 1, 2, 3 and 4 occupy the first 4 positions. If there are no 4 digit solutions and 5 must appear in position 5, there are no 5 digit solutions either.

6 digits.
123,654 - All even numbers are divisible by 2. All numbers which are divisible by 3, have the result that if you sum the digits, then that result is also divisible by 3. All numbers which are divisible by 6 are even multiples of 3. Since 1+2+3+4+5+6=21 then all even answers will be divisible by 6.
5 must appear in position 5. Even numbers must appear in even positions.
This means that the only real thing to nut out is what are those central two digits such that the result is divisible by 4 and what makes the first three digits sum to a multiple of 3.
Possible candidates for those central two digits are: 12, 16, 32 and 36, since 5 must appear in position 5 and all combinations with 4 in position 2, leave results such that the first 3 digits will never sum to a multiple of 3.
321,654 - See above.

7 digits.
I know of no simple test for divisibility of 7. They do exist but if it's too hard for me to bother with, then I don't care.
Apart from combinations of 1, 2 and 3 which work at the beginning, either 147 or 741 will also work in those first three positions since 1+4+7=12 and 12 is a multiple of 3.
Problem.
7 can replace 1 because 7-1=6 and that just means that the multiple of 6 that the sum adds to will be 6 more. 7 can not replace 3 because 7-3=4 and that means that the result will be out by 4. Therefore, the two candidates for checking are 3216547 and 1236547. Blunt force tells me that neither of these work. Therefore there are no 7 digit solutions.

8 digits.
38,165,472 - I have an 8 to play with now. 8 can replace 2 because of the problems discussed in the 7 digit problem and 7 can replace 1 as before. This would either mean that 8 or 2 are at the end. I only need to test 32165478, 32765418, 38165472 and 38765412. Only one of those works.

9 digits.
381,654,729 - All numbers which are divisible by 9, have the result that if you sum the digits, then that result is also divisible by 9. Actually this is a fundamental fact among all bases. For every base-n all numbers which are divisible by n-1, have the result that if you sum the digits, then that result is also divisible by n-1. 1+2+3+4+5+6+7+8+9=45 and 45 is a multiple of 9.
I already know that there is only one solution for 8 digits and so I know that 98,165,472 will be divisible by 8 and 981,654,723 divisible by 9, but 7 is tricksy. 9,816,547 isn't divisible by 7. Boo 7.
Chuck a 9 on the end. That doesn't upset the rest of the digits.

10 digits.
3,816,547,290 - I've only got one solution for 9 digits and all all numbers which are divisible by 10, end in 0. That's not particularly exciting but there you go.

This will more than likely be familiar to every mathematician worth their salt but for those of us down here in boring boring accountant's land where all we need to do are the the four basic operations, then this is an amusing side show.

¹ Youtube channel - https://www.youtube.com/user/standupmaths
² Website and where to buy - http://www.makeanddo4d.com/
³ Very well, your majesty - https://www.youtube.com/watch?v=1JHH6iwgIek

No comments: