Iterating squared digit sums in other bases

Posted on May 25, 2018 by Brent

In a previous post I wrote about iterating the squared digit sum function, which adds up the sum of the squares of the digits of a number; for example, s(149) = 1^2 + 4^2 + 9^2 = 1 + 16 + 81 = 98. Denis left a comment asking about other bases—what happens if we write a number in a base other than base ten and add up the squares of its digits in that base? It’s a good question, because the choice of adding up the squares of base ten digits, while natural from a human point of view, is mathematically quite arbitrary. We can sum the squares of the digits of a number written in any base.

As Denis noted in his comment, the argument from my previous post happily applies in any base, not just base 10! That is, if we consider a d-digit number in base b, the largest it can be is if it consists of d copies of the largest possible digit, which is b-1. In that case the sum of squares of its digits would be d(b-1)^2. For example, the largest sum of squares we could get with a six-digit number in base 5 is 444444, which gives us a sum of squares of 6 \cdot 4^2 = 96. But the claim is that this will be less than b^{d-1} as long as d \geq 4 and b \geq 2—which means that taking the sum of squares of the base-b digits of any number with four or more such digits will always result in a shorter base-b number. We can check that this is true when b = 2 and d = 4, since 4 \cdot 1^2 = 4 < 2^3 = 8; and intuitively, increasing either b or d will make the right-hand side increase more than the left-hand side, so it will always be true for b \geq 2 and d \geq 4. (This is an informal, hand-wavy argument—if you think you know of a way to prove it formally I would love to hear about it!)

The upshot is that for any base b \geq 2 we only have to try numbers with up to three digits to look for loops, since any bigger numbers will reduce until they have at most three digits. (One might wonder it will ever suffice to consider only two-digit numbers, when b gets large enough. The answer, perhaps surprisingly, is no. We would be looking for a base b such that 3(b-1)^2 < b^2—that is, a base for which three-digit numbers always reduce to two-digit numbers. As you can verify for yourself, the only solutions to this inequality are when b < 2! So four digits is the magic cutoff for every base b \geq 2. (I’m not going to consider negative bases here; maybe in another post.))

So I wrote a program which, for each base b, finds all the loops that happen on base-b numbers from 1 to b^3-1. It turns out that only a few bases have a single nontrivial loop, like base 10 (perhaps this is not surprising). The ones I have found are as follows. (After base 10 we quickly run out of digits; I use lowercase letters a to z to stand for digits 10 through 35, and then uppercase letters A to Z to stand for digits 36 through 61.)

  • Base 6: 32 \to 21 \to 5 \to 41 \to 25 \to 45 \to 105 \to 42
  • Base 10: 4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20
  • Base 16: a9 \to b5 \to 92 \to 55 \to 32 \to d
  • Base 20: e9, dh, 12i, g9, gh, 175, 3f, be, fh, 15e, b2, 65, 31, a, 50, 15, 16, 1h, ea, eg, 12c, 79, 6a, 6g, ec, h0
  • Base 26: o1 \to m5 \to jf \to me \to 104 \to h \to b3 \to 50 \to p
  • Base 40: 3p \to fy \to yl \to DB \to 1wa \to s5 \to k9 \to c1

Base 20 is particularly magnificent: there is a single nontrivial loop, and it has length 26!

I let my program run all the way up to base 150 (which took about 3.5 minutes on my admittedly not-so-fast laptop). Here’s some trivia:

  • After base 40, I didn’t find any more bases with only a single nontrivial loop. I conjecture there aren’t any more.
  • There are two bases tied for longest loop: base 119 and base 146 both have a loop of length 110.
  • The record holder for most loops is base 73, which has twenty-nine distinct loops into which iterating squared digit sum can fall, many of which consist of a single number: in addition to 1, each of 82, 234, 533, 1125, 1640, 2080, 2665, 2738, 3321, 3757, 4264, 4840, 5125, and 5265 is equal to the sum of squares of its own digits when written in base 73. For example, 82_{10} = 19_{73}, and sure enough, 1^2 + 9^2 = 82.

Since each number involved in a loop has at most three digits, we can think of them as coordinates in a 3d space; I wonder what the trajectories of the loops would look like! Someone should do this. A data file containing all loops up to base 150 can be found here (note that after base 61 I just start writing the numbers in base 10 again).

The program I used to search can be found here. I think my program is fairly efficient but it could probably be sped up in various ways to search much farther.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, proof and tagged , , , , . Bookmark the permalink.

7 Responses to Iterating squared digit sums in other bases

  1. John Doe says:
    May 26, 2018 at 9:07 am

    I propose the following formal argument, to prove that d (b-1)^2 \leqslant b^{d-1} if b \geqslant 1 and d \geqslant 4.

    Let’s define f_d(b) = b^{d-1} - d (b-1)^2. We now want to prove that f_d(b) \geqslant 0 on the given domain.
    We have that \frac{\partial f_d}{\partial d} = b^{d-1} \ln b - (b-1)^2 \geqslant b^{d-1} - (b-1)^2 \geqslant b^3 - (b-1)^2. The two inequalities are valid because we are only interested in a restricted domain for b and d.

    Now the degree-three polynomial b^3 - (b-1)^2 has a discriminant \Delta = -23 < 0, hence a unique real solution, which is approximatively 0.57 0, and f_d is an increasing function on its d variable.

    So now we only have to show that \forall b \geqslant 1, f_4(b) \geqslant 0. But f_4(b) = b^3-4(b-1)^2, which has a discriminant \Delta = -176 < 0. So this degree-three polynomial has one single real root, whose value is approximately 0.70 0.

    Overall, we just proved that f_d(b) \geqslant f_4(b) \geqslant 0 if d \geqslant 4 and b \geqslant 1, hence the desired result: d (b-1)^2 \leqslant b^{d-1}.

  2. projetmbc says:
    May 26, 2018 at 2:58 pm

    For the informal hand-wavy argument, studying the real function [math]f(d) = b^{d – 1} – d(b – 1)^2[/math] should do the job.

    • projetmbc says:
      May 26, 2018 at 3:53 pm

      Indeed, here is an ugly way to do the proof if I am not wrong.

      $f(d) = b^{d-1} – d(b -1)^2$ where $d \geq 4$ and $b \geq 2$

      $f ‘(d) = b^{d-1} \ln b – (b -1)^2$ increases with $d$ so let’s study the sign of $g(b) = f'(4) = b^3 \ln b – (b -1)^2$

      $g'(b) = 3 b^2 \ln b + b^2 – 2b + 2$

      $g”(b) = 6 b \ln b + 5 b – 2$

      $g”'(b) = 6 \ln b + 11$ so $g”'(b) > 0$ for $b \geq 2$

      Then we have :

      $g”(b) \geq g”(2) =12 \ln 2 + 8 > 0 $ for $b \geq 2$

      $g'(b) \geq g'(2) = 12 \ln 2 + 2 > 0$ for $b \geq 2$

      $g(b) \geq g(2) = 8 \ln 2 – 1 > 0$ for $b \geq 2$

      This gives us $f'(d) > 0$ for $d \geq 4$ and $f(d) \geq f(4) = b^3 – 4(b -1)^2$ for $d \geq 4$

      Let’s continue to be a brutal gentleman…

      Let’s study the sign of $h(b) = f(4) = b^3 – 4(b -1)^2$ for $b \geq 2$

      $h'(b) = 3 b^2 – 8 b + 8$ has clearly no no real roots and then $h'(b) > 0$ is immediate.

      Finally, $h(b) \geq h(2) = 4 > 0$ for $b \geq 2

      That’s all if no mistake has been done.

  3. Jan Van lent says:
    May 27, 2018 at 9:29 am

    I think the following argument also works to show that b^(d-1) >= d*(b-1)^2 for b >= 2 and d>=4:
    Consider b^(d-1) – d*(b-1)^2 as a function of b.
    The third derivative is.
    b^(d-4) * (d-1) * (d-2) * (d-3).
    It is easy to see that for d >= 4 this is positive for b >= 0.
    It can be checked that the third, second and first derivative are all positive at b=2.
    Therefore, to get from the third to the second derivative, we integrate a positive function, starting from a positive initial value, so the result is positive.
    Same for second to first and first to the original function of b.

    With a little bit more work, a similar argument shows that condition can be weakened to b >= 1.

  4. Anonymous says:
    May 28, 2018 at 1:44 pm

    Fun fact: in base b, there exists a two-digit number that is its own squared-digit-sum in that base if and only if b² + 1 is composite. For details and further discussion of happy bases, see the xkcd forum discussions at http://forums.xkcd.com/viewtopic.php?f=11&t=112077 and http://forums.xkcd.com/viewtopic.php?f=17&t=112118.

Comments are closed.