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
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
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.