code.kerkeslager.com Git - sandbox/blob - euler/py/0014.py

   1 """This code is the result of my attempt to solve Project Euler problem 14.  It
   2 takes a positive integer from the command line and finds the positive integer
   3 less than the given integer which starts the longest hailstone sequence.  For
   4 more information on hailstone sequences, see
   5 http://en.wikipedia.org/wiki/Collatz_conjecture .
   6
   7 While solving this problem I came across a novel usage of a few different
   8 advanced Python features for a very generalizeable and reusable way to implement
   9 memoization.  For more information on memoization, see
  10 http://en.wikipedia.org/wiki/Memoization ."""
  11
  12 class Memoize:
  13         def __init__(self,function):
  14                 self.function = function
  15                 self.memo = {}
  16
  17         def __call__(self,*arguments):
  18                 if arguments in self.memo:
  19                         return self.memo[arguments]
  20
  21                 result = self.function(*arguments)
  22                 self.memo[arguments] = result
  23                 return result
  24
  25 @Memoize
  26 def hailstone(start):
  27         if start == 1:
  28                 return 1
  29
  30         if start % 2 == 0:
  31                 return hailstone(start / 2) + 1
  32
  33         return hailstone(start * 3 + 1) + 1
  34
  35 if __name__ == '__main__':
  36         import sys
  37
  38         # Needed in order to calculate the hailstone number of large numbers.
  39         sys.setrecursionlimit(1000000)
  40
  41         limit = int(sys.argv[1])
  42         max = 1
  43         max_start = 1
  44
  45         for i in xrange(1,limit):
  46                 chain = hailstone(i)
  47
  48                 if chain > max:
  49                         max = chain
  50                         max_start = i
  51
  52         print max_start