Generate the Collatz Sequence From a Positive Integer Down to 1

The Collatz process starts from a positive integer n and repeatedly applies one rule to the current number: if it is even, divide it by 2; if it is odd, multiply it by 3 and add 1. The process stops as soon as the current number is 1. The Collatz conjecture states that the process reaches 1 from every positive starting number. It has not been proven, but it has been checked far beyond the inputs used here.

Write a function that runs the process and returns every number it visits, starting with n and ending with 1.

Function Signature

def collatz_sequence(n: int) -> list[int]:

Rules

• The first element is n and the last element is 1. Every other element is obtained from the element before it by the rule above.
• 1 appears exactly once, as the last element: the process stops at the first 1 it reaches and does not continue.
• For n = 1, return [1].

Constraints

• 1 <= n <= 10^6
• For every such n the process reaches 1, and the returned list has at most 525 elements.
• Intermediate values can exceed 2^31 - 1: the largest value reached from any starting number in this range is 56,991,483,520. All values stay far below 2^53.

Examples

Example 1

Input: n = 6
Output: [6, 3, 10, 5, 16, 8, 4, 2, 1]

6 is even, so the next value is 3. 3 is odd, so the next is 10. The process continues through 5, 16, 8, 4 and 2, and stops at 1.

Example 2

Input: n = 1
Output: [1]

The process is already at 1, so no rule is applied.

Example 3

Input: n = 7
Output: [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]