# Project Euler problem 14 solved in Python

Hi folks! I know I have been a little bit out of writing something here but today I decided to write something about coding and more particularly Project Euler and the problem 14( http://projecteuler.net/index.php?section=problems&id=14 ).

I’ve found this problem very interesting and since I didn’t had much to do I decided to solve it and make this post.

The biggest challenge of this problem its the magnitude of numbers we are trying to calculate(100000). Those who are familiar with the problem and tried a “brute force” approach to this problem knows that it might take “a while”(A LOT) to finish.

The algorithm of this approach will look something like this:

maximum = 0 max_value = 0 for value in xrange(1, 1000000): status = value terms = 0 while status > 1: if status % 2 == 0: #even status = status / 2 else: # odd status = status * 3 + 1 terms += 1 terms += 1 if terms > maximum: max_value = value maximum = terms print "value: %s terms: %s" % (max_value, maximum)

Well, don’t even try this because this is will take a lot of time to come out a result.

What we need here to solve this its a simple cache to return the number of terms from values we already know.

So, the iterative way to solve this problem comes like this:

maximum = 0 max_value = 0 SEQUENCE_CACHE = dict() for value in xrange(1, 1000000): status = value terms = 0 while status > 1: try: terms += SEQUENCE_CACHE[status] - 1 break except KeyError: pass if status % 2 == 0: #even status = status / 2 else: # odd status = status * 3 + 1 terms += 1 terms += 1 SEQUENCE_CACHE[value] = terms if terms > maximum: max_value = value maximum = terms print "value: %s terms: %s" % (max_value, maximum)

This one will take a few seconds and solve the problem. As you can see SEQUENCE_CACHE will keep track of previous results. Using this kind of cache system will allow to decrease dramatically the number of iterations required to achieve the number of terms of a certain value. Try it yourself.

As I found this problem interesting I decided to do also the recursive solution to it.

So, as before if we try a brute force recursive approach to this problem we will face the same situation, the algorithm will take a lot to finish.

This first and not correct approach will be something like:

def euler14(value, status=None, n=1): """ 'value' represents the base value 'status' represents the actual value according with odd and even forulas 'n' recursion deepness """ if status is None: status = value if status <= 1: return n if status % 2 == 0: #even status = status / 2 else: #odd status = status * 3 + 1 return euler14(value, status, n+1) terms = 0 value = 0 for x in xrange(0, 1000000): result = euler14(x) if result > terms: value = x terms = result print "value: %s terms: %s" % (value, terms)

This will take a lot of time to finish because it doesn’t take into account previous known results.

So, once again a cache enters in the play to solve the issue. If you are familiar with cache and python you know that a common use of python decorators are actually for cache and it comes in the form of @decorator_name. Our case is no different so the solution comes like:

SEQUENCE_CACHE = dict() def cache_euler14(fn): def kicker(value, status=None, n=None): try: SEQUENCE_CACHE[value] = n - 1 + SEQUENCE_CACHE[status] return SEQUENCE_CACHE[value] except (KeyError, TypeError): pass if n is None: result = fn(value, status) else: result = fn(value, status, n) if status <= 1: SEQUENCE_CACHE[value] = result return result return kicker @cache_euler14 def euler14(value, status=None, n=1): """ 'value' represents the base value 'status' represents the actual value according with odd and even formulas 'n' recursion deepness """ if status is None: status = value if status <= 1: return n if status % 2 == 0: #even status = status / 2 else: #odd status = status * 3 + 1 return euler14(value, status, n+1) terms = 0 value = 0 for x in xrange(0, 1000000): result = euler14(x) if result > terms: value = x terms = result print "value: %s terms: %s" % (value, terms)

Both solutions presented here will find the answer, no optimization was taken into account. Now, from here its just keep tracking of execution of this scripts and try to optimize it.

[apalma@insys projecteuler] time python euler14_it.py value: 837799 terms: 525 real 0m15.777s user 0m15.601s sys 0m0.128s

15 seconds…. Well Its not that hard to do beter than this but I’m tired and I’ll leave it for now. One clue: for the cache, try to use a list() instead of a dictionary.

Regards folks

Pingback: Project Euler – Problem # 14 – Solved with Python « Greg Christian's weblog