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,
given that the highest intermediate value is about 57 billion and I do
not remember that Basic had infinite precision ints.
The following iterative sequence is defined for the set of positive
integers:
n → n/2 (n is even) n → 3n + 1 (n is odd)
Note that if n is odd, 3n + 1 is even (and not 1!), so one may take two
steps with (3n + 1)/2.
Using the rule above and starting with 13, we generate the following
sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 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
win 7 machine.
from time import time
start = time()
num, max = 0, 0
for m in range(1, 1000001):
n = m
count=0
while n !=1:
if n & 1: #n % 2:
n = (3*n + 1) // 2
count += 2
else:
n = n//2
count += 1
if count > max:
num = m
max = 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
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 = n" to the odd branch, before
dividing by 2), the array would have to be limited to a much lower
value, say a few million.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
