Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
    
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
add comment

I suggest you to start reading this Wikipedia page for an explanation, and then select from Rosetta code an implementation in one of the programming languages you know and to study it. Many algorithms are either based on caching or detecting the loop 4, 16, 37, 58, 89, 145, 42, 20, 4, ...

A dynamic programming solution, implemented in Haskell, is available here.

EDIT

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.

share|improve this answer
    
Your suggested link in edit just is simple part of my algorithm, but as you can see author wrote it for 10^15 numbers, also this is competition problem, means should works in few seconds (actually I think in logarithmic order), I think there should be more elegant way. –  user742 Feb 27 '13 at 16:31
    
Yes, you are right. However, the code was written for 10^15 4 years ago, and was able to easily reach that limit in 10 minutes, so I guess that 4 years later, with appropriate hardware it can reach easily 10^18 which is the limit indicated by the OP. Of course, I understand that people have already reached 10^7000 (result taken from the same link I posted), so it is interesting anyway to devise a faster algorithm to go beyond that. –  Massimo Cafaro Feb 28 '13 at 9:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.