CODEWITHSUNDEEP
pythonalgorithm
charlie
charlie

Reputation: 187

Understanding Collatz Conjecture Objective in Python

I'm trying to decipher the following homework question. My code is supposed to evaluate to 190 but instead evaluates to 114. So, I don't think I'm understanding the coding requirement.

The Collatz conjecture is an example of a simple computational process whose behavior is so unpredictable that the world's best mathematicians still don't understand it.

Consider the simple function f(n) (as defined in the Wikipedia page above) that takes an integer n and divides it by two if n is even and multiplies n by 3 and then adds one to the result if n is odd. The conjecture involves studying the value of expressions of the form f(f(f(...f(f(n))))) as the number of calls to the function f increases. The conjecture is that, for any non-negative integer n, repeated application of f to n yields a sequence of integers that always includes 1.

Your task for this question is to implement the Collatz function f in Python. The key to your implementation is to build a test that determines whether n is even or odd by checking whether the remainder when n is divided by 2 is either zero or one. Hint: You can compute this remainder in Python using the remainder opertor % via the expression n % 2. Note you will also need to use integer division // when computing f.

Once you have implemented f, test the your implementation on the expression f(f(f(f(f(f(f(674))))))). This expression should evaluate to 190.

from __future__ import division


def collatz(n):
    l = []
    l.append(n)
    while n != 1:

        if n % 2 == 0:
            n = n // 2
            l.append(n)

        else:
            n = (3*n) + 1
            l.append(n)
    return l


print len(collatz(674))

Upvotes: 1

Views: 3028

Answers (1)

Julien
Julien

Reputation: 15081

You just misread the intermediary question. Your programs tries to answer the bigger question... This is what should return 190:

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


print f(f(f(f(f(f(f(674)))))))

Upvotes: 2

Related Questions