Math + CS = 11

I got kind of bored last night so I decided it would be a good idea to do some more playing around with Python and Project Euler. One of the problems that I really like is problem 14 and it asks to find the number under 1,000,000 which produces the longest chain when ran through the Collatz Conjecture. The idea behind the conjecture is that given the piece-wise function f(x) = x/2 if x is even or 3x+1 if x is odd, f(x) will converge down to 1 in the integers.

Here’s my Python code. I originally tried to to it with lists but it wasn’t working out so well so I decided to solve the problem using a dictionary. I also got kind of pissed when everything was off by like 1 index so I named my dictionary dick. Program outputted an answer in around 6.3 seconds. Not too bad…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def solution2(n):
    dick = {1:1}
    for i in range(2,n+1):
        count = 1
        x = i
        while i != 1:
            if dick.has_key(i):
                count = count + 1 + dick[i] - 2
                i = 1
            elif even(i):
                count = count + 1
                i = i / 2
            else:
                count = count + 1
                i = 3*i + 1
        dick[x] = count
    mysteps = max(dick.values())
    for k, v in dick.iteritems():
        if v == mysteps:
            return k