Collatz conjecture sequence

Question

The Collatz conjecture

what i am trying to do: Write a function called collatz_sequence that takes a starting integer and returns the sequence of integers, including the starting point, for that number. Return the sequence in the form of a list. Create your function so that if the user inputs any integer less than 1, it returns the empty list [].

background on collatz conjecture:

Take any natural number n. If n is even, divide it by 2 to get n / 2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

What I have so far:

def collatz_sequence(x):
    seq = [x]
    if x < 1:
       return []
    while x > 1:
       if x % 2 == 0:
         x= x/2
       else:
         x= 3*x+1 
    return seq

When I run this with a number less than 1 i get the empty set which is right. But when i run it with a number above 1 I only get that number i.e. collatz_sequence(6) returns [6]. I need this to return the whole sequence of numbers so 6 should return 6,3,10,5,16,8,4,2,1 in a list.

Answer 1

You forgot to append the x values to the seq list:

def collatz_sequence(x):
    seq = [x]
    if x < 1:
       return []
    while x > 1:
       if x % 2 == 0:
         x = x / 2
       else:
         x = 3 * x + 1 
       seq.append(x)    # Added line
    return seq

Verification:

~/tmp$ python collatz.py 
[6, 3, 10, 5, 16, 8, 4, 2, 1]

Answer 2

def collatz_sequence(x):
    seq = [x]
    while seq[-1] > 1:
       if x % 2 == 0:
         seq.append(x/2)
       else:
         seq.append(3*x+1)
       x = seq[-1]
    return seq

Here's some code that produces what you're looking for. The check for 1 is built into while statement, and it iteratively appends to the list seq.

>>> collatz_sequence(6)
[6, 3, 10, 5, 16, 8, 4, 2, 1]

Note, this is going to be very slow for large lists of numbers. A cache won't solve the speed issue, and you won't be able to use this in a brute-force solution of the project euler problem, it will take forever (as it does every calculation, every single iteration.)