Another fun fact I learned from John Cook. Let be the function which takes a positive integer and outputs the sum of the squares of its digits. For example, . Since the output is itself another positive integer, we can feed it back into the function again: . Let’s see what happens when we continue iterating in this fashion:

In this case, we hit again, after which point the values will start to repeat. So in this case, iterating enters a loop of length , where it will get stuck forever.

Let’s try another starting value, say, .

In this case we hit , which is a fixed point of , that is, , so we simply get stuck on forever.

The amazing thing is that *these are the only two things that can happen*—for *any* positive integer, iterating will eventually either reach , or enter the loop of eight numbers . Arthur Porges proved this in his article, *A Set of Eight Numbers*, published in 1945 in The American Mathematical Monthly (Porges 1945).

Let’s see a proof, inspired by Porges’s approach. First, suppose , and let be the number of digits in , so . How big could be? Since each digit contributes to the sum independently, and the digit with the biggest square is , attains its maximum possible value when consists of all ’s, in which case .

I claim that when . We can directly check that this is true when , since . And every time we increase by , the left-hand side increases by , but the right-hand side is *multiplied* by . At that rate the left-hand side can never hope to catch up!

Putting this together, we see that when has four or more digits, , which by transitivity means . In other words, if has four or more digits, necessarily makes it smaller. So if we start with some huge 500-digit number and start iterating , the results will get smaller and smaller until we finally get to a number with fewer than four digits. (A fun exercise for you: if we start with a 500-digit number, what is the maximum number of iterations of we need to reach a number with fewer than four digits?)

So what happens then? Actually, the bulk of Porges’s article is taken up with analyzing the situation for numbers of three or fewer digits. He proves various lemmas which cleverly reduce the number of cases that actually need to be checked by hand. But you see, in 1945 he didn’t have any computers to help! 1945 is right around the time when the first electronic, digital computers were being developed; it would be at least another ten or twenty years before any would have been generally available for a mathematician to use in checking a conjecture like this.

In 2018, on the other hand, it’s much faster to just write a program to test all the numbers with three or fewer digits than it is to follow Porges’s arguments. Here’s some Haskell code which does just that:

```
loop :: [Integer]
loop = [145, 42, 20, 4, 16, 37, 58, 89]
s :: Integer -> Integer
s = sum . map (^2) . map (read . (:[])) . show
ok :: Integer -> Bool
ok = any (\m -> m == 1 || m `elem` loop) . iterate s
```

The `ok`

function checks whether iterating `s`

ever produces either the number or some number in the loop. Now we just have to run `ok`

on all the numbers we want to check:

```
>>> all ok [1..1000]
True
```

And voila!

# References

Porges, Arthur. 1945. “A Set of Eight Numbers.” *The American Mathematical Monthly* 52 (7). Mathematical Association of America:379–82. http://www.jstor.org/stable/2304639.

This reminds of another fun operation similar to this one that defines ‘narcissistic numbers’… this is where you take a number and raise each digit to the number of digits and sum them. If the result is the same number then it is a narcissistic number… e.g. 8208: 8^4 + 2^4 + 0^4 +8^4 = 8208. There are only a finite set of such numbers!

Ah, fun! Yes, that does seem similar, especially the method of proving there are only finitely many.

Another problem that has that same flavour of “this must have been a lot harder when the last step was not ‘now do an easy computer search'”: a few years ago, as part of a tradition at my workplace of setting a riddle on your birthday whose answer is your age, I challenged my colleagues to find the largest integer not expressible as a sum of distinct triangular numbers.

I thought that would give them pause for thought, because they wouldn’t be able to *just* do a computer search, because how would they know it had found the largest? (Ok, so they could have stopped when they reached numbers too big to plausibly be my age, but that’s clearly not in the spirit of the challenge 🙂

My strategy was to prove inductively that all can be written as such a sum, provided we can find an integer suitable to be the base case of the induction. We don’t know what actually is at this point – but if we write down the inductive step of the proof anyway and see what conditions it demands of , we can then finish off with a computer search that quickly finds a workable value of and a list of all the cases below it that don’t work.

Do you know if this has been investigated in other bases? I did a little bit of poking myself and it looks like for in all bases greater than 2, so the first part of your proof holds. The only loop in base 3 is 002 -> 011 -> 002 and I don't think there are any loops in base 4. Further analysis will require more code.

“(b-1)^2*d is less than b^{d-1}” is true for d=4 in all bases greater than 2

Good question! I’m not aware of any such investigation (although that means very little!).

Actually, there are more loops in base 3, although 002 -> 011 -> 002 is the only one of length > 1. There is the obvious 1 -> 1 loop but there are two more as well.

Oh, yeah, I skipped those but I suppose they belong in a complete analysis 🙂 (012 and 022 – had to rederive them since I recycled my notes.) Did you end up automating the discovery?

Yes, I did — I will write up the results in a new blog post soon. Briefly, the only bases <= 20 with exactly one nontrivial loop are 6, 10, 16, and 20. (20 is particularly impressive with a loop of length 25.) I'm going to try to make my program more efficient to search higher than 20 as well.

Exciting! I look forward to seeing the post.

Pingback: Iterating squared digit sums in other bases | The Math Less Traveled

Pingback: Resumen de lecturas compartidas durante abril de 2018 | Vestigium