There is one interesting problem to solve from the guys on Project Euler.

I think that maybe there are some problems running a naive approach to the problem on the 2002, but right now, even a inefficient approach can give you results in not much time. I’ve made the following program in Python to measure the differences between a straight approach, and one using recursion and memoization. Looking carefully at the sequences, we realize that each time we get to a previous calculated number, we don’t have to recalculate the sequence again. So, doing it by hand, for the numbers from 1 to 5:

1 : 1 step 2 --> 1 : 2 steps 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1 : 8 steps 4 --> 2 --> 1: 3 steps (note that is repeated from below) 5 --> 16 --> 8 --> 4 --> 2 --> 1 : 6 steps (again, is repeated)

So, by memoization, we can store the length of previous results, so we don’t have to calculate them again.

from datetime import datetime import operator def inneficient(number): ''' Find the number of steps to 1, inefficiently ''' steps = 1 while number != 1: if number % 2 == 0: number = number / 2 else: number = number * 3 + 1 steps += 1 return steps numbers = {1:1} def efficient(number): ''' Find the number of steps to 1, nefficiently ''' if number in numbers: return numbers[number] else: if number % 2 == 0: result = efficient(number / 2) + 1 else: result = efficient(number * 3 + 1) + 1 numbers[number] = result return result def inefficient_search(times): return max(((number, inneficient(number)) for number in xrange(1, times + 1)), key=operator.itemgetter(1)) def efficient_search(times): return max(((number, efficient(number)) for number in xrange(1, times + 1)), key=operator.itemgetter(1)) def execute(function, times): time1 = datetime.now() result = function(times) time2 = datetime.now() total_time = time2 - time1 print '{0:18}: {1:9} times, time {2}. Result: {3}'.format(function.__name__, times, total_time, result) def main(): ''' Find the longest secuence of numbers ''' SMALL_NUM = 1000 BIG_NUM = 1000000 execute(inefficient_search, SMALL_NUM) execute(efficient_search, SMALL_NUM) execute(inefficient_search, BIG_NUM) execute(efficient_search, BIG_NUM) # Add another result, even bigger, to show that the complexity of the problem is not linear execute(efficient_search, BIG_NUM * 10) if __name__ == '__main__': main()

And the results on my computer:

inefficient_search: 1000 times, time 0:00:00.022727. Result: (871, 179)efficient_search : 1000 times, time 0:00:00.002074. Result: (871, 179)inefficient_search: 1000000 times, time 0:00:31.148715. Result: (837799, 525)efficient_search : 1000000 times, time 0:00:01.822361. Result: (837799, 525)efficient_search : 10000000 times, time 0:00:18.398862. Result: (8400511, 686)

So even the first option doesn’t take too long to run on a modern computer, although, of course, the second one is much faster.

PD: I get to this problem after this post from the blog of S. Lott. Includes a funny cartoon!