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!