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, . 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 -digit number in base , the largest it can be is if it consists of copies of the largest possible digit, which is . In that case the sum of squares of its digits would be . For example, the largest sum of squares we could get with a six-digit number in base 5 is , which gives us a sum of squares of . But the claim is that this will be less than as long as and —which means that taking the sum of squares of the base- digits of any number with four or more such digits will always result in a shorter base- number. We can check that this is true when and , since ; and intuitively, increasing either or will make the right-hand side increase more than the left-hand side, so it will always be true for and . (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 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 gets large enough. The answer, perhaps surprisingly, is no. We would be looking for a base such that —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 ! So four digits is the magic cutoff for *every* base . (I’m not going to consider negative bases here; maybe in another post.))

So I wrote a program which, for each base , finds all the loops that happen on base- numbers from to . It turns out that only a few bases have a single nontrivial loop, like base (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 to to stand for digits through , and then uppercase letters to to stand for digits through .)

- Base 6:
- Base 10:
- Base 16:
- Base 20:
- Base 26:
- Base 40:

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 and base both have a loop of length .
- The record holder for most loops is base , 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 , each of , , , , , , , , , , , , , and is equal to the sum of squares of its own digits when written in base . For example, , and sure enough, .

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.

I propose the following formal argument, to prove that if and .

Let’s define . We now want to prove that on the given domain.

We have that . The two inequalities are valid because we are only interested in a restricted domain for and .

Now the degree-three polynomial has a discriminant , hence a unique real solution, which is approximatively , and is an increasing function on its variable.

So now we only have to show that . But , which has a discriminant . So this degree-three polynomial has one single real root, whose value is approximately .

Overall, we just proved that if and , hence the desired result: .

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.

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.

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.

Much more pretty than my use of a function of d.

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.

Thanks for sharing this pretty fact.