#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# collatz.py
#
# Print out all numbers for which the Collatz sequence hits 1
#
# The code aims at illustrating the diagonal method
# often used to print out recursively enumerable sets.
# It is not optimized: clarity is privileged ove efficiency.
# Collatz iteration: halve if even multiply by 3 and add 1 if odd
def next_step(n):
return n // 2 if n % 2 == 0 else 3 * n + 1
# The main structure of our method, which we call a queue,
# is a dict that associates every starting value to
# the i-th entry of the corresponding sequence:
# a_1 -> a_i
# At the n-th iteration, the sequence starting from n is added to the queue;
# then, for every iteration in the queue:
# - if the iteration has reached 1, print it and remove it from the queue
# - otherwise, advance it by one step.
# The queue is initially empty
queue = {}
# Next starting value to add to the queue
n = 1
# Repeat indefinitely
while True:
# Add the initial value n of the Collatz sequence starting from n
queue[n] = n
# For all sequences that haven't reached 1
for a_1, a_i in queue.copy().items():
# if 1 has been hit
if a_i == 1:
# print the sequence and remove it from the queue
print(a_1)
del queue[a_1]
else: # not yet 1
# Advance to the next value
queue[a_1] = next_step(a_i)
# Update the starting value for the next iteration
n += 1