Is my implementation of happy number OK

[Steven D'Aprano]

On Fri, 1 May 2015 05:23 pm, Jon Ribbens wrote:

> On 2015-04-30, Dave Angel <davea at davea.name> wrote:
>> On 04/30/2015 07:31 PM, Jon Ribbens wrote:
>>> On 2015-04-30, Dave Angel <davea at davea.name> wrote:
>>>> But the real reason I didn't like it was it produced a much larger
>>>> set of happy_numbers, which could clog memory a lot sooner.  For
>>>> 10**7 items, I had 3250 happy members, and 19630 unhappy.  And Jon
>>>> had 1418854 happy members.
>>>
>>> Er, what? You're complaining that mine is less efficient by not
>>> producing the wrong output?
>>
>> It's not intended as a criticism;  you solved a different problem.  The
>> problem Cecil was solving was to determine if a particular number is
>> happy.  The problem you solved was to make a list of all values under a
>> particular limit that are happy.
>>
>> Both produce identical results for the Cecil purpose, and yours is
>> faster if one wants all the values.  But if one wants a sampling of
>> values, his function will fetch them quickly, and even if you want them
>> all, his function will use much less memory.
> 
> I must admit, I'm still not understanding. If you want to know only
> whether or not int(1e7) is happy then the calculation takes no
> measurable time or memory.

Oh, I'm sure somebody would be able to measure it...

Rather than 10**7, how about trying (10**500 + 2). Is it happy?

Using the Python code from Wikipedia:
https://en.wikipedia.org/wiki/Happy_number

SQUARE = dict([(c, int(c)**2) for c in "0123456789"])
def is_happy(n):
  while (n > 1) and (n != 4):
    n = sum(SQUARE[d] for d in str(n))
  return n == 1


I can calculate whether n=10**500 + 2 is happy in less than a millisecond on
my computer. Using your version doesn't even work, as it would require
significantly more than 1000 terrabytes of RAM just to hold the results. I
don't have that much memory.

Your version is a reasonable answer to a different question, but it doesn't
scale to very large inputs.



-- 
Steven