C++: Happy Number Endless Loop

Question

I created a function to find the first X Happy Numbers.

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1

My question is how do I know when it loops endlessly in a cycle? What I am currently doing is counting how many times it goes through the Sum Of Squares function and if it is > 10, it will just return 0. Here is my code..

C++

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

int k, rep = 0;

int SumOfSq(int num) {
    int total = 0;
    while(num) {
        int digit = num % 10;
        num /= 10;
        total += pow(digit,2);
    }
    return total;
}

bool Happy(int num) {
    int temp = 0;
    while(num != 1) {
        if(k == rep) exit(1);
        num = SumOfSq(num);
        if(temp++ > 10) {
            return 0; //Not happy
        }
    }
    rep++;
    return 1; //Happy
}

int main() {
    cout << "How many Happy Numbers to find? ";
    cin >> k;
    for(int j = 1;;j++) 
        if(Happy(j)) cout << j << " ";
}

Also please let me know if my code has any mistakes or thing to improve on. The current output should be correct.

Answer 1

From the wiki on Happy numbers:

If n is happy, then its sequence goes to 1. Otherwise, it ends in the cycle:

4, 16, 37, 58, 89, 145, 42, 20, 4, ... 

So just look to see if you have landed on one of those numbers to see if you are in the unhappy cycle.

An alternative to keeping track of the numbers you've seen, which could be better if you plan on having many cases where you travel more than 8 numbers.

Answer 2

TheGoatMan7 gives a practical answer to the question, but I figured I should add an answer explaining, at least in part, how to get there. The number of digits in a positive integer n equals floor(log n/log 10)+1. The sum of the squares of the digits of that number, then, is bounded above by 81*floor(log n/log 10 + 1). You should be able to see that when n is sufficiently large, this will be less than n. That is, when n is large, the sum of the squares of the digits of n is less than n. Let's put a loose upper bound on that cutoff:

81*floor(log 1000/log 10+1) = 81*4 < 1000

You can see now that when n > 1000, the sum of the squares of the digits on n is less than n. Whatever number you start with, you'll eventually drop under 1000 and stay there, either stabilizing or looping through numbers under 1000. So you only need to worry about numbers under 1000, and loops that last at most 1000 steps. That's just a few million operations, easily done by brute force.

---

I just saw that the underlying question is about listing happy numbers, not checking whether numbers are happy. Doing this efficiently looks complicated, but I would probably start with this fact:

Theorem

n is a happy number if and only if every number m, the sum of the squares of whose digits are n, is a happy number. Now each non-zero natural is the sum of the squares of the digits of infinitely many other naturals, so it will take some care to put all these in the right order, but I conjecture that it will end up faster. Let's see how this starts.

1 is a happy number. Therefore so are 10, 100, 1000, 10000, ...

10=1+9=2*4+2*1=4+6*1=10*1 is a happy number. Therefore, so are 13, 31, 103, 301, 1003, 3001, ..., 1122,1212,1221,2112,2121,2211,10122,10212,10221,.... 1111112,1111121,1111211,1112111,1121111,1211111,2111111,10111112,10111121,..., 1111111111,10111111111,110111111111,...

These lists, of course, would need to be merged. This approach seems to trade the complicated arithmetic of the check-each-number approach for complicated bookkeeping. I don't know if there's a way to make that worth the trouble.