Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Un-cached implementation of Project Euler problem 14. Fails to meet the "under a minute" time requirement.
#! `env python` -t
def seq(n):
"""
Generate the sequence for Project Euler problem 14.
===================================================
n is a positive integer that is the first number in the sequence.
I'm told that although it hasn't been proven, that it is believed that
regardless of the starting number, the sequence eventually gets to 1,
which is where we stop.
1 2 3 4 5 6 7 8
123456789012345678901234567989012345678901234567890123456789012345678901234567890
"""
while True:
if n % 2 == 0:
next=n/2
else:
next=3*n+1
yield n
if n == 1:
return
n=next
# end seq
def runlen(n):
"""
runlen returns the length of the sequence
generated by seq(n)
"""
count=0
for s in seq(n):
count += 1
# end "for s"
return count
#end runlen
def main():
longest=0
basis=0
for i in xrange(1, 1000000):
r=runlen(i)
if r > longest:
basis=i
longest=r
# print 'runlen(', i,')=', runlen(i)
# end "for i"
print "longest=", longest,\
"generated from", basis
return basis
# end main
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment