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