Collatz sequence steps with memoized range maximum

Define steps(n) as the number of transformations needed to take n to 1
(even: halve it; odd: 3n + 1). So steps(1) = 0, steps(2) = 1,
steps(3) = 7. The reported question has two parts: compute steps(n) for one
number, then find the largest steps(k) over every k in [1, n].

Part 1: one number. Simulate. Loop while n != 1, apply the rule, count.
Validate input: the process is only defined for positive integers.

Part 2, brute force. Call steps(k) for each k from 1 to n and keep the
maximum. Correct, but every chain re-walks values that earlier chains already
measured. Chains are long (steps(27) = 111), so this repeats a lot of work.

Part 2, optimal: memoize the chain. The key fact is that
steps(k) = 1 + steps(next(k)). Once any value's step count is known, every
chain that reaches it can stop there. For each starting k:

1. Walk forward from k, pushing each unseen value onto a path list, until we
   hit a value whose count is already cached (1 is cached as 0).
2. Unwind the path backwards: each value's count is one more than the value
   after it. Cache every value on the path.

Invariants:

• Every cached value maps to its exact step count.
• The walk always terminates at a cached value (assuming the conjecture, which
  is verified far beyond any interview input).
• The walk is iterative, so a long chain cannot overflow the recursion stack.

Chains climb far above n (starting under 10,000, values pass 27 million), so
the cache is a dict. A list of size n + 1 that only caches small values is a
common, faster variant: values above n are simulated without caching (see Follow-ups).

Ties: when two starting values share the maximum count, return the smallest one.
State this choice out loud; interviewers accept either if it is stated.

from typing import Dict, List, Tuple


def collatz_next(n: int) -> int:
    return n // 2 if n % 2 == 0 else 3 * n + 1


def collatz_steps(n: int) -> int:
    """Number of transformations needed to take n to 1."""
    if n < 1:
        raise ValueError("n must be a positive integer")
    count = 0
    while n != 1:
        n = collatz_next(n)
        count += 1
    return count


class CollatzSolver:
    """Answers many step-count queries, sharing work through a cache."""

    def __init__(self) -> None:
        self._cache: Dict[int, int] = {1: 0}

    def steps(self, n: int) -> int:
        if n < 1:
            raise ValueError("n must be a positive integer")
        path: List[int] = []
        current = n
        while current not in self._cache:
            path.append(current)
            current = collatz_next(current)
        count = self._cache[current]
        for value in reversed(path):
            count += 1
            self._cache[value] = count
        return self._cache[n]

    def longest_up_to(self, n: int) -> Tuple[int, int]:
        """Return (start, steps) with the most steps for start in [1, n].

        Ties go to the smallest start.
        """
        if n < 1:
            raise ValueError("n must be a positive integer")
        best_start, best_steps = 1, 0
        for start in range(1, n + 1):
            s = self.steps(start)
            if s > best_steps:
                best_start, best_steps = start, s
        return best_start, best_steps


def longest_brute_force(n: int) -> Tuple[int, int]:
    best_start, best_steps = 1, 0
    for start in range(1, n + 1):
        s = collatz_steps(start)
        if s > best_steps:
            best_start, best_steps = start, s
    return best_start, best_steps


if __name__ == "__main__":
    assert collatz_steps(1) == 0
    assert collatz_steps(2) == 1
    assert collatz_steps(6) == 8
    assert collatz_steps(7) == 16
    assert collatz_steps(27) == 111
    solver = CollatzSolver()
    assert solver.steps(27) == 111
    assert solver.steps(9) == 19
    assert solver.longest_up_to(1) == (1, 0)
    assert solver.longest_up_to(10) == (9, 19)
    assert solver.longest_up_to(100) == (97, 118)
    assert solver.longest_up_to(1_000_000) == (837799, 524)
    for n in range(1, 300):
        assert CollatzSolver().longest_up_to(n) == longest_brute_force(n)
    try:
        collatz_steps(0)
        raise AssertionError("expected ValueError")
    except ValueError:
        pass
    print("all tests pass")

Let L(k) be the chain length of k (no closed form; empirically it grows
roughly like log k, and the max below 10^6 is 524).

• collatz_steps(n): O(L(n)) time, O(1) space.
• CollatzSolver.steps(n): O(L(n)) the first time, but only the part of the
  chain not yet cached is walked. A cached value answers in O(1).
• longest_up_to(n), brute force: O(sum of L(k) for k ≤ n), about
  O(n log n) in practice. For n = 10^6 that is about 130 million steps.
• longest_up_to(n), memoized: each distinct value on any chain is walked
  once, so time is O(number of distinct values visited). That is a small
  constant times n in practice (a few million for n = 10^6). Space is the same
  as the time, because each visited value is cached. The path list is
  O(max L(k)).

• collatz_steps(1) -> 0 (already at 1).
• collatz_steps(2) -> 1.
• collatz_steps(6) -> 8 (6, 3, 10, 5, 16, 8, 4, 2, 1).
• collatz_steps(7) -> 16.
• collatz_steps(27) -> 111 (the classic long chain from a small start).
• collatz_steps(0) or a negative number -> ValueError.
• longest_up_to(1) -> (1, 0).
• longest_up_to(10) -> (9, 19).
• longest_up_to(100) -> (97, 118).
• longest_up_to(1_000_000) -> (837799, 524); should finish in a couple of
  seconds with the cache.
• Calling steps many times on one solver gives the same answers as fresh
  solvers (the cache never stores a wrong value).
• Memoized result equals brute force for every n below 300.

1. Return the sequence, not just the count. Walk the chain and collect
   values; O(L(n)) extra space. To rebuild it from the cache, store the next
   value only, since next(k) is cheap to recompute. No cache change needed.
2. Many queries, or a very large n. A dict of millions of Python ints uses
   a lot of memory. Use a fixed array of size n + 1 and cache only values
   ≤ n; values above n are simulated without storing them. This is usually 3–5x
   faster and has bounded memory. Use n >> 1 and 3n + 1 with bit checks for
   a further constant speedup. For n beyond memory, compute in chunks; the
   answer for a range only needs the running maximum.
3. Combine odd steps. When n is odd, 3n + 1 is even, so jump straight
   to (3n + 1) / 2 and count 2 steps. Also, for any even k, steps(k) = steps(k / 2) + 1, so the maximum over [1, n] is reached by some start
   above n / 2; the scan can skip the lower half.
4. Recursion vs iteration. A recursive memoized version is shorter, but
   chains can be hundreds of steps deep and Python's recursion limit is 1000.
   Explain why the iterative path-unwinding version is safer.
5. What if the conjecture failed? A start that cycles or diverges would
   loop forever. Add a step budget or cycle detection (a set of values on the
   current path, or Floyd's algorithm) and report the start as unresolved.
   Also discuss concurrency: the cache can be shared across threads because
   every write is the same correct value, so races are harmless.

Mid-level (L4)

• Writes the single-number loop correctly, including steps(1) = 0 and input
  validation.
• Gets to the range maximum with brute force, then adds a cache when asked why
  it is slow.
• States time and space plainly and tests small cases by hand.

Senior (L5)

• Proposes memoization unprompted, using steps(k) = 1 + steps(next(k)), and
  fills the whole path in one pass.
• Notices that chains exceed n and picks a dict, or a bounded array with
  uncached overflow, and explains the trade-off.
• Avoids deep recursion and defines the tie-break rule explicitly.

Staff (L6+)

• Discusses memory at scale (millions of cached ints), bounded caches, and
  the "skip the lower half" observation.
• Handles the theoretical non-termination case with a budget or cycle check.
• Frames the cache as a reusable service (many queries, shared across threads,
  precomputed table) and reasons about when precomputation pays off.