Project Euler 14: (Iron)Python
- by Ben Griswold
In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 14.
As always, any feedback is welcome.
# Euler 14
# http://projecteuler.net/index.php?section=problems&id=14
# The following iterative sequence is defined for the set
# of positive integers:
# n -> n/2 (n is even)
# n -> 3n + 1 (n is odd)
# 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. Which starting number,
# under one million, produces the longest chain?
# NOTE: Once the chain starts the terms are allowed to go
# above one million.
import time
start = time.time()
def collatz_length(n):
# 0 and 1 return self as length
if n <= 1: return n
length = 1
while (n != 1):
if (n % 2 == 0):
n /= 2
else:
n = 3*n + 1
length += 1
return length
starting_number, longest_chain = 1, 0
for x in xrange(1, 1000001):
l = collatz_length(x)
if l > longest_chain: starting_number, longest_chain = x, l
print starting_number
print longest_chain
# Slow 31 seconds
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')
