0

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?

Improve this question
10
  • 2
    Recursion is (almost?) never the most efficient solution, if straightforward iterative approaches exist. Also, it's frowned upon to ask three questions in one question. Commented Dec 7, 2014 at 20:23
  • This 'challenge' is known as the Collatz conjecture. Commented Dec 7, 2014 at 20:25
  • I accept the -1 for asking three question in one, but why the other -1? Commented Dec 7, 2014 at 20:26
  • @SamHammamy Yeah Im looking for that answer actually. I got -4 for I just wrote Python as python. Nice users ha :-) Commented Dec 7, 2014 at 20:27
  • Recursion is tricky with Python because there is always a limit on how many times a function is allowed to call itself without returning. By default, this limit is 1000. So, if you enter a number that will produce a chain longer than 1000, you'll get an error. Commented Dec 7, 2014 at 20:56

3 Answers 3

Reset to default
3

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
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

So its "obviously" not faster, but its fun...got it.
@ScottHunter faster than OP's version :)
In certain cases, recursion is much easier to read, as in the factorial example for instance. The question wasn't fun vs not-fun, but rather speed and readability
"Would that improve efficiency?" was the original question; this "answer" brought in the question of fun (in a playful way, but still).
0

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

Improve this answer

7 Comments

But if it can't be proven that it will halt how can it have O(N) complexity
@AnuragUniyal Really? It seems you're blindly replacing concrete with general. It the same as you would say "That's an NP-hard problem" by looking at 2SAT.
@manzur: Yes, really. You can't establish how many times the loop will execute, because sometimes n increases (for example, n=3). In fact, its a pretty famous open problem whether or not the function is defined for all n.
@ScottHunter sure, but my evaluation is for the function I wrote, not for 3n+1.
@manzur: But your technique does not apply to this problem, and thus is not appropriate in an answer to it.
|
0
  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.
Improve this answer

5 Comments

Disagreed on 1. With this problem, recursion is an opportunity to use memoization, which can provide a significant speedup when you avoid redoing work. So it is possible for recursion to improve efficiency, particularly if you're doing a wide range. That said, rewriting a recursive version to an iterative form will probably be a speedup.
And memoization can't be done w/o recursion because...?
@ScottHunter, The usual meaning of memoization is based around function calls. Since there is only one function call without recursion, memoization won't help. You can (and should) use dynamic programming though
A simple cache would do the job nicely.
@ScottHunter I find it easier to initially implement memoization with recursion. But I agree that rewriting that version iteratively would be likely to improve performance.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.