# Count unhappy numbers in a large interval

An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1.

For example, $23\rightarrow 2^2+3^2 = 13 \rightarrow 1^2 + 3^2 = 1$, so $23$ is a happy number. But, number $2$ is not and you can verify it.

The problem around my question (from 2010 acp icpc problem set) is to count unhappy numbers in an interval $[\textrm{lo}, \textrm{hi}]$. I'm looking for an algorithm that is practical for $\textrm{hi}$ up to $10^{18}$.

How can I write an algorithm for this problem, efficient and correct?

I know that the solution is with dynamic programming, but I don't know how can I get it.

My approach when I read the problem was use a backtracking to mark all numbers in the interval, like a dfs, and see that when you're processing a number and got the result, you should mark all numbers with form permutations of digits for the initial number. Then, I thought that a backtracking approach is faster. But this is not enough for contest, because the interval is $[1, 10^{18}]$ so, clearly dynamic programming is the way.

-
Please a) define the problem completely and b) get rid of all the python; you should distill out the important pieces and give them as pseudo code. Then, you can flag for reopening. –  Raphael Feb 26 '13 at 7:38
What is the sum of squares digit map? Please provide a clearer definition of the problem that doesn't require reading external links. –  Joe Feb 26 '13 at 19:11

Because sum of square of digits of 18 digit number is smaller than or equal to $18\times 9^2 = 1458$, it's enough to enumerate first $1458$ numbers and find list of happy numbers out of them (we say it $happy-list$), then for a given range $[lo,hi]$ check each number's square digit sum is in our happy list or not, so this is $O(hi-lo)$, because you can do preprocessing and save happy numbers below $1458$, then use them, but this is not good because when $lo=0, hi=10^{18}$ the $O(hi-lo)$ algorithm is not good for current PCs, so is better to find number of solution for below equation:

$x_1^2+....x_{18}^2 = y_i \forall y_i \in happy-list \text{ and } x_j >0$.

I don't know if is there any straight forward way to do this, but we know something like number of solution for $x_1+....x_{18} = y_i \forall y_i \in happy-list\text{ and } x_j >0$ is easy to find. I wrote this because I think this gives an idea to how to start to think about this problem, but if I found a way for above equation or with similar idea, I'll update my answer, but my first answer is too much faster than recursion like wiki's solution.

-
Thanks, yes, there is a straightforward way, I didn't understand with this code, ser.cs.fit.edu/ser2012/problems/division_1/I_unhappy/UNHAPPY.py –  d555 Feb 27 '13 at 18:58
The C source code available here uses the GNU GMP library to test for happiness of very large numbers. You can use it to test far beyond $10^{18}$, assuming you have enough memory. The code is for windows, but is easily portable to linux and Mac OS X.