math for love

(Click here for Part I or Part II)

Recall the puzzle:

Step 1: Choose a starting number.

Step 2: Square the number.

Step 3: Sum up the digits of that number.

Step 4: Repeat steps 2 and 3 until you understand what’s going on.

and recall that we had three discovered loops, which we called the 1 loop, the 9 loop, and the 13-16 loop. The question was: are these the only loops?

Today, the solution to the puzzle.

First thing: what we don’t want to do here is check every number; that would take, literally, till the end of time. So our first priority in this case is to limit the amount of work we need to do. There’s a nice way to do this, it turns out, and it hinges on noticing that for most large numbers, taking a digit sum reduces the size of a number much faster than squaring a number increases its size.

A thought experiment: if you have a 50 digit number, what’s the largest it could be after you square it and then take it’s digit sum? In the worst case, all fifty digits would be 9s, which means it’s one less than a one followed by fifty zeroes (or 10^50). Squaring that latter number is easy: it’s just a one followed by 100 zeroes (10^100). So our number must be less than that, which means it has at most 100 digits (and in general, squaring a number roughly doubles the number of digits it contains).

Now let’s take the digit sum.  The greatest digit sum a hundred digit number could have is 9+9+…+9 one hundred times, or 900. Meaning if we start with a 50 digit number, we’ll be down to a three digit number in no time. From three digit number, we square to six digit number, and then take the digit sum to at most 54. If you follow this logic, you can see that no matter how large a number you start with, you’ll end up below 60 (or below 30 or so, if you want to continue) at some point, so all you need to do is check the first 60 (or 30 or so) numbers and see if they end up in one of those loops. I’ll leave the details to you, but I’ve checked, and there are indeed only three loops that numbers less than 60 end up in, so hence only three possible loops.

That’s a pretty nice argument*, I think. There’s more to this problem, though, like, is there any quick way to tell which loop a number ends up in? The answer is yes: it turns out that if you just take the digit sum over and over and forget squaring, it won’t affect which loop you end up in. In other words, 7561 ends up in the same loop as its digit sum, 19, which ends up in the same digit sum as its digit sum, 10, which ends up in the same loop as its digit sum 1. In other words, 7561 ends up in the 1 loop.

Here’s why: digit sums have a very nifty quality: they tell you when a number is divisible by 9 (remember the divisibility rule?). For example, 5904 has a digit sum of 18, which is divisible by 9… therefore 5904 is divisible by 9. Nifty, right? (Now any curious seeker of mathematical patterns will immediately want to know how this could possibly be true. I’m not going to answer that question here, but think about it. You can also check this out.)

In fact, digit sums are even better: they don’t change the remainder of a number divided by 9. For example, 5904 had remainder 0; so did its digit sum. 496 has the same remainder as its digit sum, which is 19, which has remainder 1 when divided by 9.

Now talking about remainders when you divide by 9 is so annoying to type that I’d like to shorten it. Let’s call a numbers remainder when divided by 9 that number “mod 9.” So 19 = 1 (mod 9). Also, 496 = 1 (mod 9). (I’d like to say 496 = 19 (mod 9) as well, since that’s how I like equals signs to work… but I suppose that my definition doesn’t quite allow it. Or does it? Is there a better definition I could have used?)

In any case, let’s look at this puzzle in mod 9. This is kind of like looking at the shadow of the numbers as they travel through the dr square puzzle. They sometimes lurch up or down, but they might seem to stay the same to us if we only care about their mod 9 shadow. Let’s see what happens.

41 –> 1681 –> 16 –> 256 –> 13 –> 169 –> 16 –> (13-16 loop)

(and in the shadow version mod 9, where 41 = 5)

5 –> 7 –> 7 –> 4 –> 4 –> 7 –> 7 –> …

Now this is interesting. First of all, it’s much simpler–which makes sense, since we’ve cut out a lot of information. Second of all, we seem to get repeated numbers. But that makes perfect sense. We already knew that taking the digit sum doesn’t change a number’s mod 9 shadow, so we’ll have to get repetition. This means that the only chance to change the mod 9 shadow comes when we square the number. What are the options when we square the numbers mod 9? Well, there’s not much work to do to find the loops. Of course, we have to remember to cross out the numbers above 9 and replace them with the mod 9 shadows.

0 –> 0 –> etc.

1 –> 1 –> etc.

2–> 4 –> 16  7 –> 49  4 –> 7 –> 4 –> etc.

3 –> 9 0 –> 0 –> etc.

4 –> 7 –> 4 –> 7–> etc. (we saw this loop already, up two lines)

5 –> 25 7 –> 4 –> etc.

6 –> 36 0 –> 0 –> etc.

7 –> 4 –> etc.

8 –> 64 1 –> 1 –> 1

Notice that we have only three loops in the mod 9 world. We might call them the 0 loop, the 1 loop, and the 4 – 7 loop. Might these correspond to the loops we saw before? In fact, they do: we even called them the same thing, except the 4-7 loop, which we called the 13-16 loop (notice the digit sum of 13 is 4, and the digit sum of 16 is 7). Since we know from our earlier argument that there are only three loops, we can tell from here which loop we end up in just by taking the digit sum. In other words, 187 has digit sum 16, which has digit sum 7, which means it has to end up in a loop that includes 7 (mod 9), and the only option is the 13-16 loop. So we shouldn’t be surprised to see that happens when we check it out:

187 –> 34969 –> 31 –> 961 –> 16 –> 256 –> 13 –> …

So that’s it!

Here’s a followup puzzle, which I call the DR Square Plus One.

Step 1: Choose a starting number.

Step 2: Square the number, and then add 1.

Step 3: Sum up the digits of that number.

Step 4: Repeat steps 2 and 3 until you understand what’s going on.

Can you find all the loops? Can you predict which loop a number might end up in?

I think the DR Square Plus One is an even neater puzzle than the previous. The solution is even a bit tidier than it’s predecessor.

Enjoy!

*For those who are interested, here’s the higher power mathematical method to show that you don’t need to test numbers higher than 30 (in fact, 26) to find the loops in the DR Square problem. Let x be your starting number. Your next two steps will take you to x^2, and then to something less than 9log(x^2) = 9(2log x) = 18 log(x). (Here log is log base 10.) We can see that 18 log(x) > x will be true only if x is sufficiently small, and playing around with this will give us a bound. For example, x = 100, gives 18log(x) = 36, which means we can assume that x must be less than 36. Iterating or graphing gives us the final result that we only need to check up to x < 26.