The conjecture of 8

The other day I found an amusing short from numberphile about “happy numbers”. Not unlike the Collatz problem, a number is happy if, through successive transformations, it reaches one. The transformation is rather numerological in nature (i.e., it’s arbitrary and so why not): To get the next number in the series to happiness, you take the current number and sum the squares of its digits.

The example in the video is that 7 is a happy number:

7 \to 7^2=49

49 \to 4^2+9^2=97

97 \to 9^2+7^2=130

130 \to 1^2+3^2+0^2=10

10 \to 1^2+0^2=1

Therefore 7 is a happy number. That’s cool, but are all numbers happy, and, if not, what happens when a number is unhappy?

Let us see. First, we need to implement the “numerological transform”:

int happisum(int x)
 {
  int s=0;
  while (x)
   {
    int d=x % 10;
    x/=10;
    s+=sqr(d);
   }
  return s;
 }

This function combines conversion to base 10 with summing the squares of the digits (and let’s remark that it is safe even for large numbers: the maximum sum of squares isn’t very large). Then we need a function that tests a specific number for its eventual return to one. We can make the hypothesis that all numbers are happy, in which case checking against 1 is sufficient for a halting condition. If, on the contrary, hypothesize that not all numbers are happy, then two things are possible: either the series diverges, or it has cycles. Diverging is impossible, so that means that unhappy numbers form cycles.

The simplest possible implementation looks something like this:

void happihappi_cycle(int x)
 {
  std::map<int,int> seen;
  int c=0;
  while (x!=1)
   {
    c++;
    int s=happisum(x);
    std::cout << " " << s;
    x=s;
    if (seen.find(x)!=seen.end())
     {
      std::cout << " X L=" << c-seen[x];
      break;
     }
    else
     seen[x]=c;
   }
  std::cout << std::endl;
 }

This code checks for cycles and their lengths. The output for the first few numbers:

1
2   4 16 37 58 89 145 42 20 4 X L=8
3   9 81 65 61 37 58 89 145 42 20 4 16 37 X L=8
4   16 37 58 89 145 42 20 4 16 X L=8
5   25 29 85 89 145 42 20 4 16 37 58 89 X L=8
6   36 45 41 17 50 25 29 85 89 145 42 20 4 16 37 58 89 X L=8
7   49 97 130 10 1
8   64 52 29 85 89 145 42 20 4 16 37 58 89 X L=8
9   81 65 61 37 58 89 145 42 20 4 16 37 X L=8
10  1

Unhappy numbers are marked by X then follows the cycle length. The first few have length 8. What about the others? Does it go on forever? Let us see for the first 100M numbers. The command

happi | grep --text X | cut -d= -f 2 | sort -u

…only outputs 8.

*
* *

As soon as the series reaches any one of these:

145 42 20 4 16 37 58 89

the series forms a cycle of length 8 (in the order above) and the number is unhappy.

Conjecture: All unhappy numbers produce cycles of length 8: 145 42 20 4 16 37 58 89.

To demonstrate the above conjecture, one has to show that happy numbers avoid the 8 numbers listed. I guess it could be done constructively by starting by 1, then enumerating its predecessors (in the numerological transform order), then all their predecessors, until all numbers under 4 (or maybe 5) digits are accounted for, except for the 8 above, and their predecessors.

To be continued…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: