pythoncollatz

How to check if sequence cycles or repeats


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?


Solution

  • 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 268, so checking if n == 1 is enough in practice.