Collatz conjecture

The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1.

It is named after the mathematician Lothar Collatz, who introduced the idea in 1937, two years after receiving his doctorate.

"[7] Jeffrey Lagarias stated in 2010 that the Collatz conjecture "is an extraordinarily difficult problem, completely out of reach of present day mathematics".

[8] However, though the Collatz conjecture itself remains open, efforts to solve the problem have led to new techniques and many partial results.

[8][9] Consider the following operation on an arbitrary positive integer: In modular arithmetic notation, define the function f as follows:

Now form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.

The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

Therefore, computer searches to rule out cycles that have a small lowest term can strengthen these constraints.

This yields a heuristic argument that every Hailstone sequence should decrease in the long run, although this is not evidence against other cycles, only against divergence.

The argument is not a proof because it assumes that Hailstone sequences are assembled from uncorrelated probabilistic events.

In 2019, Terence Tao improved this result by showing, using logarithmic density, that almost all (in the sense of logarithmic density) Collatz orbits are descending below any given function of the starting point, provided that this function diverges to infinity, no matter how slowly.

Responding to this work, Quanta Magazine wrote that Tao "came away with one of the most significant results on the Collatz conjecture in decades".

[9][18] In a computer-aided proof, Krasikov and Lagarias showed that the number of integers in the interval [1,x] that eventually reach 1 is at least equal to x0.84 for all sufficiently large x.

[clarification needed] There is another approach to prove the conjecture, which considers the bottom-up method of growing the so-called Collatz graph.

Then in binary, the number n can be written as the concatenation of strings wk wk−1 ... w1 where each wh is a finite and contiguous extract from the representation of ⁠1/3h⁠.

[24] Conjecturally, every binary string s that ends with a '1' can be reached by a representation of this form (where we may add or delete leading '0's to s).

Repeated applications of the Collatz function can be represented as an abstract machine that handles strings of bits.

Using this form for f(n), it can be shown that the parity sequences for two numbers m and n will agree in the first k terms if and only if m and n are equivalent modulo 2k.

The Collatz map can be extended to (positive or negative) rational numbers which have odd denominators when written in lowest terms.

In this context, assuming the validity of the Collatz conjecture implies that (1 0) and (0 1) are the only parity cycles generated by positive whole numbers (1 and 2, respectively).

[28] He showed that the conjecture does not hold for positive real numbers since there are infinitely many fixed points, as well as orbits escaping monotonically to infinity.

Since this expression evaluates to zero for real integers, the extended function is an interpolation of the Collatz map to the complex plane.

The corresponding Julia set, shown on the right, consists of uncountably many curves, called hairs, or rays.

[30] For example, if k = 5, one can jump ahead 5 steps on each iteration by separating out the 5 least significant bits of a number and using This requires 2k precomputation and storage to speed up the resulting calculation by a factor of k, a space–time tradeoff.

For the special purpose of searching for a counterexample to the Collatz conjecture, this precomputation leads to an even more important acceleration, used by Tomás Oliveira e Silva in his computational confirmations of the Collatz conjecture up to large values of n. If, for some given b and k, the inequality holds for all a, then the first counterexample, if it exists, cannot be b modulo 2k.

Some properties of the Syracuse function are: The Collatz conjecture is equivalent to the statement that, for all k in I, there exists an integer n ≥ 1 such that fn(k) = 1.

In 1972, John Horton Conway proved that a natural generalization of the Collatz problem is algorithmically undecidable.

Kurtz and Simon[34] proved that the universally quantified problem is, in fact, undecidable and even higher in the arithmetical hierarchy; specifically, it is Π02-complete.

[36][37] The connection is made through the Busy Beaver function, where BB(n) is the maximum number of steps taken by any n state Turing machine that halts.

Hence if BB(15) was known, and this machine did not stop in that number of steps, it would be known to run forever and hence no counterexamples exist (which proves the conjecture true).