Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder7.xlned.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: Python 3.3 vs. MSDOS Basic
Date: Mon, 18 Feb 2013 19:50:51 -0500
References: <e8a634af-4e29-4f45-b327-2dfd1fab5269@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: quoted-printable
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130107 Thunderbird/17.0.2
In-Reply-To: <e8a634af-4e29-4f45-b327-2dfd1fab5269@googlegroups.com>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1986.1361235083.2939.python-list@python.org>
Lines: 82
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:39148

On 2/18/2013 2:13 PM, John Immarino wrote:
> I coded a Python solution for Problem #14 on the Project Euler
> website. I was very surprised to find that it took 107 sec. to run
> even though it's a pretty simple program.  I also coded an equivalent
> solution for the problem in the old MSDOS basic. (That's the 16 bit
> app of 1980s vintage.)  It ran in 56 sec. Is there a flaw in my
> coding, or is Python really this slow in this particular application.
> MSDOS Basic usually runs at a snails pace compared to Python.

I find this surprising too. I am also surprised that it even works,=20
given that the highest intermediate value is about 57 billion and I do=20
not remember that Basic had infinite precision ints.

> The following iterative sequence is defined for the set of positive
> integers:
>
> n =E2=86=92 n/2 (n is even) n =E2=86=92 3n + 1 (n is odd)

Note that if n is odd, 3n + 1 is even (and not 1!), so one may take two=20
steps with (3n + 1)/2.

> Using the rule above and starting with 13, we generate the following
> sequence: 13 =E2=86=92 40 =E2=86=92 20 =E2=86=92 10 =E2=86=92 5 =E2=86=92=
 16 =E2=86=92 8 =E2=86=92 4 =E2=86=92 2 =E2=86=92 1
>
> It can be seen that this sequence (starting at 13 and finishing at 1)
> contains 10 terms. Although it has not been proved yet (Collatz
> Problem), it is thought that all starting numbers finish at 1.

https://en.wikipedia.org/wiki/Collatz_conjecture

> Which starting number, under one million, produces the longest
> chain?

I suppose 'print(837799)' would not count as a proper solution.

> NOTE: Once the chain starts the terms are allowed to go above one
> million.

Here is my slightly revised code with timings on a good, 20 month old=20
win 7 machine.

from time import time
start =3D time()

num, max =3D 0, 0
for m in range(1, 1000001):
     n =3D m
     count=3D0
     while n !=3D1:
         if n & 1:  #n % 2:
             n =3D (3*n + 1) // 2
             count +=3D 2
         else:
             n =3D n//2
             count +=3D 1
     if count > max:
          num =3D m
          max =3D count

print(num, max , time()-start)

# original: 837799, 524 steps, 53.9 secs
# for ... range: 52.3
# reverse inner if 49.0
# double step 39.1
# n & 1 instead of n % 2 for test: 36.0, 36.0,  35.9
# n>>1  instead of n//2: 34.7, 36.1, 36.2;
# this may be internally optimized, so skip

I do not see any fluff left to remove, unless one takes the major step=20
of saving already calculated values in an array.

Since the highest intermediate value of n is 56991483520 (445245965
*2**7, from adding "if n > maxn: maxn =3D n" to the odd branch, before=20
dividing by 2), the array would have to be limited to a much lower=20
value, say a few million.

--=20
Terry Jan Reedy