How to check if sequence cycles or repeats

Question

I have a program that generates numbers of the 3n + 1 problem. The program takes a value of n and iterates until n becomes 1.

n = 49

number = n
current_iter = 0 
computed_nums = [n] 
iterations = [0]
while n != 1:
    if n % 2 == 0:
        n = (n / 2)
    else:
        n = ((n * 3) + 1)
    current_iter += 1
    computed_nums.append(n)
    iterations.append(current_iter)

print("Computed numbers: " + str(computed_nums))
print("Iterations required: " + str(current_iter))

How can I check if the sequence ever cycles or repeats?

Answer 1

You just need to keep track of which numbers you've already visited and check if n is one of them.

n = 49

computed_nums = {}
while n not in computed_nums:
    if n % 2 == 0:
        res = n // 2
    else:
        res = n*3 + 1
    computed_nums[n] = res
    n = res  # For next loop

print(list(computed_nums))
print("Iterations:", len(computed_nums)-1)

Output:

[49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Iterations: 24

Here I'm using a dict, which preserves insertion order as of Python 3.7.

Note: The Collatz conjecture has been tested up to 2⁶⁸, so checking if n == 1 is enough in practice.