Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.005 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'memory.': 0.07; 'nicely': 0.07; 'lookup': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'subject:number': 0.09; 'python': 0.11; 'def': 0.12; 'random': 0.14; 'digits)': 0.16; 'iteration': 0.16; 'received:80.91.229.3': 0.16; 'received:dip0.t-ipconnect.de': 0.16; 'received:plane.gmane.org': 0.16; 'received:t-ipconnect.de': 0.16; 'subject:happy': 0.16; 'worst': 0.16; 'wrote:': 0.18; 'trying': 0.19; 'examples': 0.20; 'header:User-Agent:1': 0.23; 'case.': 0.24; 'second': 0.26; 'header:X-Complaints-To:1': 0.27; 'am,': 0.29; "doesn't": 0.30; 'code': 0.31; 'url:wiki': 0.31; "d'aprano": 0.31; 'steven': 0.31; 'subject:skip:i 10': 0.31; 'url:wikipedia': 0.31; 'cases': 0.33; 'computer.': 0.33; 'fri,': 0.33; 'table': 0.34; 'but': 0.35; 'really': 0.36; 'sequence': 0.36; 'url:org': 0.36; 'should': 0.36; 'example,': 0.37; 'needed': 0.38; 'to:addr:python-list': 0.38; 'rather': 0.38; 'to:addr:python.org': 0.39; 'enough': 0.39; 'received:org': 0.40; 'how': 0.40; 'even': 0.60; 'ian': 0.60; 'most': 0.60; 'tell': 0.60; 'took': 0.61; 'simple': 0.61; 'maximum': 0.63; 'skip:n 10': 0.64; '500': 0.70; 'square': 0.74; '2015': 0.84; 'reasoning': 0.91 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Peter Otten <__peter__@web.de> Subject: Re: Is my implementation of happy number OK Date: Fri, 01 May 2015 20:13:20 +0200 Organization: None References: <87oam5vc8k.fsf@Equus.decebal.nl> <554338dd$0$13004$c3e8da3$5496439d@news.astraweb.com> Mime-Version: 1.0 Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7Bit X-Gmane-NNTP-Posting-Host: p57bd85d4.dip0.t-ipconnect.de User-Agent: KNode/4.13.3 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 41 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1430504017 news.xs4all.nl 2950 [2001:888:2000:d::a6]:50260 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:89744 Ian Kelly wrote: > On Fri, May 1, 2015 at 2:27 AM, Steven D'Aprano > wrote: >> 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. > > Not really the most exciting example, since the following number in > the sequence would be 5. But a random sequence of 500 non-zero digits > doesn't seem to take substantially longer. I may be missing something, but isn't the '+ 2' in '10**500 + 2' just a distraction? 10**500 would bring across nicely what the approach Steven took from Wikipeda can do in one iteration where Jon's cannot even find enough memory. Also, with 500 digits and 0 <= d <= 9 sum(d*d for d in digits) <= 81 * 500 should hold, i. e. on the second iteration the maximum number of digits is already down to five in the worst case. By repeating this simple reasoning you can tell that all interesting examples must be below 1000 as num_digits(3*81) == 3. A computer that cannot calculate a lookup table with all 3-digit cases should be almost as hard to find as the one needed by Jon ;)