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.
Count unhappy numbers in a large interval
algorithms;dynamic programming