3n+1 Programming Challenge in Python

Question

The 3n+1 challenge is quite popular and can be found here

I've created a solution in python below and also here on github

def solution(i, j):
    count = toRtn = 1
    for n in xrange(i, j+1):
        count = 1
        while n != 1:
            if n % 2 == 0:
                n = n/2
            else:
                n = (3 * n) + 1
            count += 1
        toRtn = max(toRtn, count)
    return toRtn

print solution(100, 200)
print solution(201, 210)

I have several questions:

1. Can and should this be re-written as a recursion? Whould that improve efficiency?

2. How can I calculate the complexity of this function?

3. Is there an online judge for Python for those challenges?

Answer 1

You can define a recursive method to calculate 3n+1

def threen(n):
    if n ==1:
        return 1
    if n%2 == 0:
        n = n/2
    else:
        n = 3*n+1
    return threen(n)+1

To avoid calculating same numbers twice you can cache values

cache = {}
def threen(n):
    if n in cache:
        return cache[n]
    if n ==1:
        return 1
    orig = n
    if n%2 == 0:
        n = n/2
    else:
        n = 3*n+1
    count = threen(n)+1
    cache[orig] = count
    return count

Now you can use this in a loop

def max_threen(i, j):
    max3n = 0
    for n in xrange(i, j+1):
        max3n= max(threen(n), max3n)
    print i, j, max3n

max_threen(100,201)

Now you can compare this with your version :), it may consume a lot of memory but could be faster for certain ranges, obviously a non recursive method would be faster if you are caching values, but recursion is fun and more readable, but in anycase iterative version will be faster with caching (not tested)

cache = {}
def solution(i, j):
    count = toRtn = 1
    for n in xrange(i, j+1):
        count = 1
        orig = n
        if n in cache:
            count = cache[n]
        else:
            while n != 1:
                if n % 2 == 0:
                    n = n/2
                else:
                    n = (3 * n) + 1
                count += 1

            cache[orig] = count
        toRtn = max(toRtn, count)
    return toRtn

Answer 2

1. No and no; recursion is rarely (if ever) used for better performance.
2. You can't, since it hasn't even been established that it will return for all values of n. (Nobody has found one that it doesn't return for, but no one has proved that there isn't one, either.)
3. Not to my knowledge.

Answer 3

1) Strictly speaking recursion itself can't optimize itself. Recursion is not about optimization, but about clarity when needed. However you could use recursion with memoization to boost the performance: http://en.wikipedia.org/wiki/Memoization

2) Complexity of the function sum of the complexity of each of its statements. So to calculate the whole complexity you should construct a table of two columns for each line: [Number of times called], [Complexity] and sum up each of the row. Let's look at the following code:

 def print_N_times(N):
    print "------"        #Line1
    for i in range(0,N):  #Line2
        print "easy"      #Line3
    print "------"        #Line4 

-------------------------------------------------------
| Line number | Number of times executed | Complexity | 
|  Line 1     |        1                 |     1      |
|  Line 2     |        N+1               |     1      |
|  Line 3     |        N                 |     1      |
|  Line 4     |        1                 |     1      |
-------------------------------------------------------

(Here 1 is as a replacement for constant complexity)

So by multiplying each column and summing them up:

1*1 + (N+1)*1 + N*1 + 1*1 = 2*N + 3 = O(N), so this function has linear complexity.

3) There're a lot of judges, but spoj.pl accepts variety of programming languages:

http://www.spoj.com/problems/PROBTRES/

Edit: Correctly noted in comments that for 3n+1 problem you don't know each value of the [Number of times of executed] column, or whether the function will be finished ever. For more info see:

https://en.wikipedia.org/wiki/Collatz_conjecture