by **phw** » Mon Jun 04, 2018 5:20 am

This is a property of arithmetic modulo 9. It's easier to explain if you know a little number theory, but you don't need much so I'll try to explain it without assuming anything.

Let's only be concerned with the remainder when each number is divided by 9.

You describe two operations. Adding the base 10 digits of a number doesn't change it's remainder when dividing by 9. (Why? because if you have a number like a + 10b + 100c + ... and subtract a+b+c+..., you get 0 + 9b + 99c + ... which is obviously a multiple of 9. If a number minus the sum of its digits is a multiple of 9, then they have the same remainder.)

The other operation doubles a number, which after dividing by 9, naturally both doubles the quotient which we're ignoring and also doubles the remainder.

That means that the order you do the digitsums and doubles in doesn't matter, only how many times you double. Let's test that by redoing your example with 8. Doubling it three times gives 8-->16-->32-->64 which has remainder 1 because 64 = 9*7 + 1.

As you observed, you can't get back to 1 if you start with a multiple of 3. That's because if you double a multiple of 3, it will still be a multiple of 3 and it's remainder when divided by 9 can only be 0, 3, or 6. Also if you double a number which is not a multiple of 3, it still won't be a multiple of 3, so you can never get into a 3-6 cycle unless you start there.

OK, so why does it work in every other case. Let's try starting with 1 and just keep on doubling, tracking only the remainders mod 9. 1--> 2--> 4--> 8--> 16=7--> 14=5--> 10=1. It's a 124875 cycle that repeats indefinitely, and it contains every remainder except for the multiples of 3 that we knew wouldn't show up. How many doublings it takes to get back to 1 just depends on where in the cycle you start.

Incidentally, the fact that doubling generates the longest possible cycle is a special and somewhat unusual property of mod 9. If you use another base, you might not get back to 1. For example, using base 16 and starting with 7, you get 7--> E--> 1C=D --> 1A=B -->16=7. You get a cycle, but it's shorter than you hoped and notably doesn't include 1 which lives in a different cycle ( 1--> 2 -->4 -->8 --> 10=1).