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 |

Problem 14


#! /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

  

jb