Katana VentraIP

Collatz conjecture

The Collatz conjecture[a] is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×1020, but no general proof has been found.

It is named after the mathematician Lothar Collatz, who introduced the idea in 1937, two years after receiving his doctorate.[4] The sequence of numbers involved is sometimes referred to as the hailstone sequence, hailstone numbers or hailstone numerals (because the values are usually subject to multiple descents and ascents like hailstones in a cloud),[5] or as wondrous numbers.[6]


Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."[7] Jeffrey Lagarias stated in 2010 that the Collatz conjecture "is an extraordinarily difficult problem, completely out of reach of present day mathematics".[8]

If the number is even, divide it by two.

If the number is odd, triple it and add one.

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.


In notation: (that is: ai is the value of f applied to n recursively i times; ai = fi(n)).


The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially. That is, for each , there is some with .


If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not contain 1. Such a sequence would either enter a repeating cycle that excludes 1, or increase without bound. No such sequence has been found.


The smallest i such that ai < a0 is called the stopping time of n. Similarly, the smallest k such that ak = 1 is called the total stopping time of n.[2] If one of the indexes i or k doesn't exist, we say that the stopping time or the total stopping time, respectively, is infinite.


The Collatz conjecture asserts that the total stopping time of every n is finite. It is also equivalent to saying that every n ≥ 2 has a finite stopping time.


Since 3n + 1 is even whenever n is odd, one may instead use the "shortcut" form of the Collatz function: This definition yields smaller values for the stopping time and total stopping time without changing the overall dynamics of the process.

Directed graph showing the orbits of the first 1000 numbers.

Directed graph showing the orbits of the first 1000 numbers.

The x axis represents starting number, the y axis represents the highest number reached during the chain to 1. This plot shows a restricted y axis: some x values produce intermediates as high as 2.7×107 (for x = 9663)

The x axis represents starting number, the y axis represents the highest number reached during the chain to 1. This plot shows a restricted y axis: some x values produce intermediates as high as 2.7×107 (for x = 9663)

The same plot as the previous one but on log scale, so all y values are shown. The first thick line towards the middle of the plot corresponds to the tip at 27, which reaches a maximum at 9232.

The same plot as the previous one but on log scale, so all y values are shown. The first thick line towards the middle of the plot corresponds to the tip at 27, which reaches a maximum at 9232.

The tree of all the numbers having fewer than 20 steps.

The tree of all the numbers having fewer than 20 steps.

The number of iterations it takes to get to one for the first 100 million numbers.

Collatz Conjecture 100M

Extensions to larger domains

Iterating on all integers

An extension to the Collatz conjecture is to include all integers, not just positive integers. Leaving aside the cycle 0 → 0 which cannot be entered from outside, there are a total of four known cycles, which all nonzero integers seem to eventually fall into under iteration of f. These cycles are listed here, starting with the well-known cycle for positive n:


Odd values are listed in large bold. Each cycle is listed with its member of least absolute value (which is always odd) first.

Optimizations

Time–space tradeoff

The section As a parity sequence above gives a way to speed up simulation of the sequence. To jump ahead k steps on each iteration (using the f function from that section), break up the current number into two parts, b (the k least significant bits, interpreted as an integer), and a (the rest of the bits as an integer). The result of jumping ahead k is given by

For all kI, f(4k + 1) = f(k). (Because 3(4k + 1) + 1 = 12k + 4 = 4(3k + 1).)

In more generality: For all p ≥ 1 and odd h, fp − 1(2ph − 1) = 2 × 3p − 1h − 1. (Here fp − 1 is .)

function iteration notation

For all odd h, f(2h − 1) ≤ 3h − 1/2

If k is an odd integer, then 3k + 1 is even, so 3k + 1 = 2ak with k odd and a ≥ 1. The Syracuse function is the function f from the set I of positive odd integers into itself, for which f(k) = k (sequence A075677 in the OEIS).


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 popular culture

In the movie Incendies, a graduate student in pure mathematics explains the Collatz conjecture to a group of undergraduates. She puts her studies on hold for a time to address some unresolved questions about her family's past. Late in the movie, the Collatz conjecture turns out to have foreshadowed a disturbing and difficult discovery that she makes about her family.[35][36]

3x + 1 semigroup

Arithmetic dynamics

Modular arithmetic

Residue-class-wise affine group

Matthews, Keith. .

"3 x + 1 page"

An ongoing project Archived 2021-08-30 at the Wayback Machine by David Bařina verifies Convergence of the Collatz conjecture for large values. (furthest progress so far)

volunteer computing

() volunteer computing project Archived 2017-12-04 at the Wayback Machine that verifies the Collatz conjecture for larger values.

BOINC

An ongoing volunteer computing by Eric Roosendaal verifies the Collatz conjecture for larger and larger values.

project

Another ongoing volunteer computing by Tomás Oliveira e Silva continues to verify the Collatz conjecture (with fewer statistics than Eric Roosendaal's page but with further progress made).

project

"Collatz Problem". MathWorld.

Weisstein, Eric W.

at PlanetMath..

Collatz Problem

Nochella, Jesse. . Wolfram Demonstrations Project.

"Collatz Paths"

(8 August 2016). Uncrackable? The Collatz conjecture (short video). Numberphile. Archived from the original on 2021-12-11 – via YouTube.

Eisenbud, D.

(August 9, 2016). Uncrackable? Collatz conjecture (extra footage). Numberphile. Archived from the original on 2021-12-11 – via YouTube.

Eisenbud, D.

(featuring) (30 July 2021). The simplest math problem no one can solve (short video). Veritasium – via YouTube.

Alex Kontorovich

Are computers ready to solve this notoriously unwieldy math problem?