Generate the Collatz Sequence From a Positive Integer Down to 1
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
Input: n = 1
Output: [1]
```
The process is already at 1, so no rule is applied.
**Example 3**
```text
Input: n = 7
Output: [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
```
Overview: Write a function that runs the Collatz process from a positive integer, halving even values and replacing odd values with three times the value plus one, and returns every number visited until reaching 1. It tests loop termination, edge cases such as a start of 1, and intermediate values beyond 32-bit range.