My solutions to the problems found at Project Euler.
Jump to: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 16 | 17 | 20 | 21 | 22 | 25 | 3-2 |#! /usr/bin/
# Problem: Find the largest sequence generated by a number under a million
# using the following conditions:
#
# n -> n/2 (when n is even)
# n -> 3n + 1 (when n is odd)
#
# It's conjectured that this will always end at 1.
#
# Approach: I'm going to see how slow brute-force is, and then optimize from there.
#
# Note: Cool! It runs in a pretty reasonable amount of time.
# I made some assumptions here:
#
# a) Our answer would be in the top 20% of our number.
# b) It would be odd.
#
# It worked out well, although I haven't tested it
# for other solutions, so I could have been completely
# lucky. :) If anything, I can add a collatz sequence
# generator to my things of "oh yeah I know
# what that is."-list
def collatz(n):
seq = [n]
while not n == 1:
if n % 2 == 0:
n /= 2
else:
n = n*3 + 1
seq.append(n)
return seq
if __name__ == "__main__":
highest = (0,0) #(seqlen, n)
target = 1000000
if target % 2 == 0:
max_range = target-1
else:
max_range = target
min_range = int(target * 0.8)
for n in xrange(max_range,min_range,-2):
l = len(collatz(n))
if l > highest[0]:
highest = (l,n)
print highest