Collatz sequence steps with memoized range maximum

Starting from a positive integer n, repeat the following until n equals 1:

• If n is even, set n = n / 2.
• If n is odd, set n = 3n + 1.

Each replacement counts as one step. (It is widely believed, though unproven, that every positive integer reaches 1.)

Part 1. Implement collatz_steps(n: int) -> int, which returns the number of steps needed to reach 1. collatz_steps(1) is 0. Raise an error for n < 1.

Part 2. Implement longest_up_to(n: int) -> tuple[int, int], which returns (start, steps) for the starting value in [1, n] that needs the most steps. If several starts tie, return the smallest. Your solution should handle n up to 1,000,000 in a few seconds, so avoid recomputing work that earlier starting values already did.

Example 1

collatz_steps(6) -> 8
# 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Example 2

longest_up_to(10) -> (9, 19)
# 9 needs 19 steps; no start from 1 to 10 needs more.

Constraints

• 1 <= n <= 10^6 for Part 2.
• Intermediate values can grow far larger than n (starting from 27, the sequence climbs past 9,000).