Collatz conjecture

Although the conjecture has not been proven, most mathematicianscounterexamples may be found when considering very large positive integers, as in the case of the disproven Pólya conjecture and Mertens conjecture.

However, such verifications may have other implications. Certain constraints on any non-trivial cycle, such as lower bounds on the length of the cycle, can be proven based on the value of the lowest term in the cycle. Therefore, computer searches to rule out cycles that have a small lowest term can strengthen these constraints.

If one considers only the odd numbers in the sequence generated by the Collatz process, then each odd number is on average ⁠3/4⁠ of the previous one. (More precisely, the geometric mean of the ratios of outcomes is 2-adic extension of the Collatz process has two division steps for every multiplication step for almost all 2-adic starting values.)

As proven by Riho Terras, almost every positive integer has a finite stopping time. In other words, almost every Collatz sequence reaches a point that is strictly below its initial value. The proof is based on the distribution of parity vectors and uses the central limit theorem.

In 2019, Terence Tao improved this result by showing, using logarithmic density, that almost all (in the sense of logarithmic density) Collatz orbits descend 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".

In a computer-aided proof, Krasikov and Lagarias showed that the number of integers in the interval A cycle is a sequence where simple continued fraction expansion of

There is another approach to prove the conjecture, which considers the bottom-up method of growing the so-called Collatz graph, a graph defined by the inverse relation

So, instead of proving that all positive integers eventually lead to 1, we can try to prove that 1 leads backwards to all positive integers. For any integer if and only iftree for positive integers except for the 1–2–4 loop (the inverse of the 4–2–1 loop of the unaltered function Statement of the problem section of this article).

When the relation

For any integer power of 2 that divides remainder). The resulting function odd numbers to odd numbers. Now suppose that for some odd number binary, the number stringsrepetends of abstract machine that handles strings of bits. The machine will perform the following three steps on any odd number until only one 1 remains:

1. Append binary as

   If

   Hailstone sequences can be computed by the 2-tag system with production rules

   CycleOdd-value cycle lengthFull cycle length1 → 4 → 2 → 1...13−1 → −2 → −1...12−5 → −14 → −7 → −20 → −10 → −5...25−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17...718

   The generalized Collatz conjecture is the assertion that every integer, under iteration by 2-adic integers, which contains the ring of rationals with odd denominators as a subring.

   When using the "shortcut" definition of the Collatz map, it is known that any periodic parity sequence is generated by exactly one rational. Conversely, it is conjectured that every rational with an odd denominator has an eventually cyclic parity sequence (Periodicity Conjecture).

   If a parity cycle has length

   For example, the parity cycle as the latter leads to the rational cycle

   Any cyclic permutation of

   For a one-to-one correspondence, a parity cycle should be irreducible, that is, not partitionable into identical sub-cycles. As an illustration of this, the parity cycle

The function is well-defined on the ring of 2-adic integers, where it is continuous and measure-preserving with respect to the 2-adic measure. Moreover, its dynamics is known to be ergodic.

Define the parity vector function as

The function isometry. Consequently, every infinite parity sequence occurs for exactly one 2-adic integer, so that almost all trajectories are acyclic in .

An equivalent formulation of the Collatz conjecture is that

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 ofA075677 in the OEIS).

Some properties of the Syracuse function are:

• For all function iteration notation.)
• For all odd John Horton Conway proved that a natural generalization of the Collatz problem is algorithmically undecidable.

  Specifically, he considered functions of the form where halting problem in this way.

  Closer to the Collatz problem is the following universally quantified problem:

  Given arithmetical hierarchy; specifically, it is equal to zero, are formalized in an esoteric programming language called FRACTRAN.

The Collatz and related conjectures are often used when studying computational complexity. 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. There is a 15-state Turing machine that halts if and only if the following conjecture by Paul Erdős (closely related to the Collatz conjecture) is false: for all n > 8 there is at least one digit 2 in the base 3 representation of 2ⁿ. 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). This is a completely impractical way to settle the conjecture; instead it is used to suggest that BB(15) will be very hard to compute, at least as difficult as settling this Collatz-like conjecture.

In 2024, a six-state machine was found for which determining whether it halts involves solving a Collatz-like problem called the antihydra problem. As proofs of even simple conjectures of this nature are not currently known, this suggests that BB(6) will be very hard to compute.