Interesting Project Euler problem

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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s