Another fun fact I learned from John Cook. Let $s(n)$ be the function which takes a positive integer and outputs the sum of the squares of its digits. For example, $s(149) = 1^2 + 4^2 + 9^2 = 1 + 16 + 81 = 98$ . Since the output is itself another positive integer, we can feed it back into the function again: $s(98) = 9^2 + 8^2 = 81 + 64 = 145$ . Let’s see what happens when we continue iterating in this fashion:

$149 \to 98 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89 \to 145 \to \dots$

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

Let’s try another starting value, say, $496$ .

$496 \to 133 \to 19 \to 82 \to 68 \to 100 \to 1 \to 1 \to \dots$

In this case we hit $1$ , which is a fixed point of $s$ , that is, $s(1) = 1^2 = 1$ , so we simply get stuck on $1$ forever.

The amazing thing is that these are the only two things that can happen—for any positive integer, iterating $s$ will eventually either reach $1$ , or enter the loop of eight numbers $(145,42,20,4,16,37,58,89)$ . 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 $n \geq 1000$ , and let $d$ be the number of digits in $n$ , so $10^{d-1} \leq n$ . How big could $s(n)$ be? Since each digit contributes to the sum independently, and the digit with the biggest square is $9$ , $s(n)$ attains its maximum possible value when $n$ consists of all $9$ ’s, in which case $s(n) = 9^2 + 9^2 + \dots + 9^2 = 81d$ .

I claim that $81d < 10^{d-1}$ when $d \geq 4$ . We can directly check that this is true when $d = 4$ , since $81 \cdot 4 = 324 < 10^3 = 1000$ . And every time we increase $d$ by $1$ , the left-hand side increases by $81$ , but the right-hand side is multiplied by $10$ . At that rate the left-hand side can never hope to catch up!

Putting this together, we see that when $n$ has four or more digits, $s(n) \leq 81d < 10^{d-1} \leq n$ , which by transitivity means $s(n) < n$ . In other words, if $n$ has four or more digits, $s$ necessarily makes it smaller. So if we start with some huge 500-digit number and start iterating $s$ , 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 $s$ 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 $1$ 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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

12 Responses to Iterating squared digit sum

Naren Sundar says:

May 1, 2018 at 9:30 pm

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!
- Brent says:
  
  May 1, 2018 at 9:35 pm
  
  Ah, fun! Yes, that does seem similar, especially the method of proving there are only finitely many.
Simon Tatham says:

May 2, 2018 at 7:02 am

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 $n>N$ can be written as such a sum, provided we can find an integer $N$ suitable to be the base case of the induction. We don’t know what $N$ actually is at this point – but if we write down the inductive step of the proof anyway and see what conditions it demands of $N$ , we can then finish off with a computer search that quickly finds a workable value of $N$ and a list of all the cases below it that don’t work.
Denis says:

May 8, 2018 at 1:04 pm

Do you know if this has been investigated in other bases? I did a little bit of poking myself and it looks like $(b-1)^2*d < b^{d-1}$ for $d=4$ 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.
- Denis says:
  
  May 8, 2018 at 1:07 pm
  
  “(b-1)^2*d is less than b^{d-1}” is true for d=4 in all bases greater than 2
- Brent says:
  
  May 8, 2018 at 9:49 pm
  
  Good question! I’m not aware of any such investigation (although that means very little!).
- Brent says:
  
  May 11, 2018 at 8:57 am
  
  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.
  - Denis says:
    
    May 11, 2018 at 9:06 am
    
    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?
    - Brent says:
      
      May 11, 2018 at 9:19 am
      
      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.
      - Denis says:
        
        May 11, 2018 at 9:47 am
        
        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