콜라츠 수열

Lothar Collatz was born in Arnsberg, in Westphalia, in 1910, and took his doctorate in Berlin in 1935 under Alfred Klose. His published career was in applied mathematics — numerical analysis, eigenvalue estimates, differential equations — first at the Technical University of Hanover and then at Hamburg, where he founded the Institute of Applied Mathematics. He is remembered for none of that. He is remembered for a problem he posed in 1937, two years after his doctorate, and never published.

That omission shaped everything that followed. The problem spread by word of mouth and picked up a new name wherever it landed. Collatz is reported to have passed it around orally at the International Congress of Mathematicians in Cambridge, Massachusetts, in 1950, and to have described it to Helmut Hasse in Hamburg in 1952. Hasse took to it, and according to Jeffrey Lagarias's survey of the literature it was Hasse who proposed calling it the Syracuse problem, during a visit to Syracuse University. Elsewhere it is Ulam's conjecture, after Stanisław Ulam; Kakutani's problem, after Shizuo Kakutani; the Thwaites conjecture, after Bryan Thwaites; or Hasse's algorithm. Plainest of all, it is the 3n+1 problem. Nothing about it appeared in the mathematical literature until the early 1970s.

The names multiplied because the proofs did not. The rule interleaves multiplication and division in a way that defeats the standard tools: no quantity decreases monotonically, and there is no algebraic structure to lean on. Paul Erdős's much-quoted verdict was that "mathematics may not be ready for such problems" — the variant "is not yet ready for such problems" also circulates.

What progress exists is statistical. In 2019 Terence Tao showed that, measured by logarithmic density, almost all starting values have orbits that eventually sink below any function you care to name, so long as it grows to infinity; the work was published as "Almost all orbits of the Collatz map attain almost bounded values" in Forum of Mathematics, Pi in 2022. Brute force has gone further in its narrower way: every start below 2^68 had been checked by 2020, and David Barina raised the verified limit to 2^71, about 2.36 × 10^21, in 2025. Not one counterexample has turned up.

주요 성질

• The rule: halve n when it is even, replace it with 3n+1 when it is odd. The conjecture — still unproved — is that every positive integer eventually reaches 1.
• Starting from 27 the trajectory takes 111 steps and climbs to 9,232 before falling to 1. No smaller starting number needs more than 23 steps.
• Stopping time is wildly non-monotone: 27 takes 111 steps while its neighbour 28 takes 18.
• Powers of two are the dull case — 2^k simply halves k times, so it finishes in exactly k steps.
• Doubling a start adds exactly one step: 2n halves straight back to n, so the total stopping time of 2n is always one more than that of n.
• A rise is never followed by a rise: 3n+1 is even whenever n is odd, so every tripling step is immediately followed by a halving.
• Below one million, 837,799 has the longest trajectory at 524 steps, and 704,511 climbs the highest, reaching 56,991,483,520.
• Every trajectory that reaches 1 then cycles 1 → 4 → 2 → 1. No other cycle is known, and the computer search rules out any cycle containing a number below 2^71.

등장하는 곳

• Project Euler problem 14 asks which starting number below one million produces the longest Collatz chain; the answer is 837,799, with 524 steps.
• The iteration is a standard first exercise in programming courses, usually under the name "hailstone numbers" — the values rise and fall like a hailstone carried up and down inside a storm cloud.
• It is the textbook example in program-termination analysis: a four-line loop whose termination nobody can prove. John Conway showed in 1972 that a natural generalisation of the rule produces undecidable problems, so no single algorithm can settle every variant.
• Searching for a counterexample has become a benchmark for GPU-accelerated integer arithmetic; David Barina’s open-source verification code holds the current record.
• The xkcd strip numbered 710, titled "Collatz Conjecture", made the problem a joke about mathematical obsession — a measure of how far outside mathematics it has travelled.