Take a positive integer and keep applying one rule until you reach 1: halve it if it is even, otherwise triple it and add one. The number of rule applications is the number's Collatz steps. For example 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 takes 8 steps, and 1 takes 0.
Implement two functions:
collatz_steps(n: int) -> int: the steps for onen(1 <= n <= 10**15; intermediate values may grow far pastn).longest_chains(limits: list[int]) -> list[tuple[int, int]]: for eachLinlimits, the starting numberxin1..Lwith the most steps, and that step count, as(x, steps). On a tie, the smallestxwins. Answers come back in the order oflimits.
collatz_steps(6) # 8
collatz_steps(1) # 0
collatz_steps(27) # 111
longest_chains([1, 3, 10, 6]) # [(1, 0), (3, 7), (9, 19), (6, 8)]
limits can hold 100,000 values, each up to 500,000. Walking every chain from scratch repeats the same tails millions of times and is far too slow.
Show hint
Compute steps for every number up to max(limits) in increasing order into a list. When the walk from n drops below n, the rest of the chain is already known: add the stored count and stop. Then a running "best so far" per L answers each query in O(1).