Collatz problem

The Collatz problem , also known as the (3n + 1) conjecture , is an unsolved mathematical problem that was posed by Lothar Collatz in 1937 . It has connections to number theory , to the theory of dynamic systems and ergodic theory and to the theory of computability in computer science .

The problem is considered notoriously difficult, even though it is easy to phrase. Jeffrey Lagarias , who is considered an expert on the problem, cited an oral communication from Paul Erdős , who described it as "absolutely hopeless".

Problem

Bar chart for the numbers 1 to 100 million. It shows how often a certain length of the Collatz sequence occurs.

The problem is about sequences of numbers that are constructed according to a simple law of formation:

• Start with any natural number . ${\displaystyle n>0}$
• Is straight, so take next . ${\displaystyle n}$ ${\displaystyle n/2}$
• If odd, take next . ${\displaystyle n}$ ${\displaystyle 3n+1}$
• Repeat the process with the number you received.

For example, you get the sequence for the starting number ${\displaystyle n=19}$

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...

Apparently the sequence ends with each of them in cycle 4, 2, 1. The Collatz conjecture reads: ${\displaystyle n>0}$

Every sequence of numbers constructed in this way leads to cycle 4, 2, 1, regardless of which natural number you start with. ${\displaystyle n>0}$

Despite much effort, this conjecture is still one of the unsolved problems in mathematics . Several prizes were awarded for a solution:

• In 1970 HSM offered Coxeter $ 50 for a proof of the conjecture and $ 100 for a counterexample.
• In 1982, Bryan Thwaites promised £ 1,000 for evidence or rebuttal in The Times newspaper (offer renewed in 1996/1998).
• Paul Erdős allegedly offered $ 500 for a solution and said of the Collatz problem:

"Mathematics is not yet ready for such problems." ("Mathematics is not yet ready for such problems.") And

"Hopeless. Absolutely hopeless. "(" Hopeless. Absolutely hopeless. ")

The mathematician Richard Guy warned in 1983 about this and three other problems that are still unsolved today:

“Don't try to solve these problems!” (“Don't try to solve these problems!”)

Origin and history

The origin of the Collatz conjecture is somewhat in the fog, as so far no written documents describing the problem are publicly available from the presumed time of origin. It is reported that Collatz orally spread the problem at the 1950 International Congress of Mathematicians in Cambridge, Massachusetts . Stanisław Ulam and Shizuo Kakutani , who were invited to give lectures at this congress, repeatedly presented the problem in discussions and are therefore frequently mentioned in this context. When Lothar Collatz took up his professorship in Hamburg in 1952, he told his Hamburg colleague Helmut Hasse about the assumption. This spread the problem during a research stay at Syracuse University , so the Collatz problem was also called the Syracuse conjecture . Publications on the creation and distribution:

• In 1971 the Collatz problem was probably first published in writing in the printed version of a lecture given by HSM Coxeter in 1970.
• 1972 learned Martin Gardner from the employment of academic hackers at MIT with the (3n + 1) problem and described it in his column Mathematical Games in Scientific American . The conjecture became widely known within and outside of specialist circles through this and other publications, among others by John Conway .
• In 1976 Riho Terras published the first scientific research results directly on the Collatz problem.
• In 1985, a review article by Jeffrey Lagarias appeared in the American Mathematical Monthly . In it Lagarias reports on Collatz's interest in number theoretic functions and graph theory, and he cites a notebook entry from July 1, 1932, in which Collatz considers the following permutation of positive integers:

${\displaystyle g(n)={\begin{cases}{\tfrac {2}{3}}n&{\text{wenn}}\quad n\equiv 0\mod 3,\\{\tfrac {4}{3}}n-{\tfrac {1}{3}}&{\text{wenn}}\quad n\equiv 1\mod 3,\\{\tfrac {4}{3}}n+{\tfrac {1}{3}}&{\text{wenn}}\quad n\equiv 2\mod 3.\end{cases}}}$

This permutation has the fixed point 1 and also at least the cycles (2, 3), (4, 5, 7, 9, 6) and (44, 59, 79, 105, 70, 93, 62, 83, 111, 74, 99, 66). In the quoted entry in the notebook, Collatz asks the question, which is still open today, whether the g - trajectory beginning with 8 becomes cyclical or diverges towards infinity. The question of whether further cycles exist, which is also still open, is like the (3n + 1) conjecture one of the problems described by Guy that one should not try to solve.

• In 1985 Bryan Thwaites published a notice that he had made the conjecture on July 21, 1952 at four o'clock in the afternoon as a task for the entertainment of his students (he claimed the 1952 discovery as early as 1982).
• In 1986 Lothar Collatz had a description of his path of discovery about the (3n + 1) conjecture translated into Chinese and published in the journal of a university in Qufu , Shandong, China, where he had given a lecture on it. This was the only publication by Collatz on this problem.

After Terras' publication in 1976, a lively scientific preoccupation with the Collatz problem began, which now includes well over a hundred publications with new research results. In the popular science area, new terms were created:

• 1979 named Douglas Hofstadter in his book Gödel, Escher, Bach those start numbers whose Collatz trajectory ends in the cycle (1,4,2), wondrous numbers , miraculous numbers .
• 1984 Brian Hayes called the numbers Collatz sequences in the column computer recreations in Scientific American hailstone numbers , hailstorms numbers .

Collatz graph of a function

Excerpt from the Collatz graph for the Collatz function

Collatz's description of his motivation for the (3n + 1) conjecture is very plausible: he initially associates a directed graph in general for any function on the natural numbers with values ​​in the natural numbers , that of Lagarias in the above-mentioned overview article Collatz graph is called. The Collatz graph of a number theoretic function

${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$

is a directed graph , consisting of the set of natural numbers as a vertex set and for every natural number of a directed edge from to . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f(n)}$

The simplest such function is the successor mapping

${\displaystyle s\colon \mathbb {N} \to \mathbb {N} ,\quad s(n)=n+1,}$

whose Collatz graph consists of an infinitely long path:

${\displaystyle 1\to 2\to 3\to 4\to 5\to \dotsb }$

In order to have more examples, he first looked for a "simple" number theoretic function whose Collatz graph contains a circle . Such a function must “rise” on certain natural numbers , that is, fulfill the relation , and “descend” on other natural numbers , that is, fulfill the relation . So he first came across the function that is defined by ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle n<f(n)}$ ${\displaystyle m}$ ${\displaystyle m>f(m)}$

${\displaystyle C_{1}(n):={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\n+1\quad &{\text{wenn }}n{\text{ ungerade ist.}}\end{cases}}}$

The Collatz graph of this function can be described as follows: The nodes are, by definition, the positive integers. If the node is straight, it has the two previous nodes and , otherwise only . Also applies ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle 2k}$ ${\displaystyle 2k}$

${\displaystyle C_{1}^{2}(n)=C_{1}(C_{1}(n))={\begin{cases}{\frac {n}{4}}&{\text{wenn }}n{\text{ durch 4 teilbar ist,}}\\{\frac {n}{2}}+1&{\text{wenn }}n{\text{ durch 2, aber nicht durch 4 teilbar ist,}}\\{\frac {n+1}{2}}\quad &{\text{wenn }}n{\text{ ungerade ist.}}\end{cases}}}$

It follows

${\displaystyle C_{1}^{2}(n)<n\qquad {\text{ wenn }}n>2,}$

and that has the consequence that the Collatz graph of only has the circle and that the trajectory ends in this circle at any starting number. ${\displaystyle C_{1}}$ ${\displaystyle (1,2)}$ ${\displaystyle C_{1}}$

Because this reasoning is quite simple, Collatz looked further: The Collatz graph of the function

${\displaystyle C_{2}(n)={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\2n+1\quad &{\text{wenn }}n{\text{ ungerade ist,}}\end{cases}}}$

does not contain a circle, since every odd number is mapped to a larger odd number and the trajectories therefore all diverge towards infinity. ${\displaystyle C_{2}}$

The next attempt is the Collatz function

${\displaystyle C\colon \mathbb {N} \to \mathbb {N} ,\quad C(n)={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\3n+1&{\text{wenn }}n{\text{ ungerade ist.}}\end{cases}}}$     (Follow A006370 in OEIS )

Collatz only found the "trivial circle" for this function - he wrote that he had not published his ideas because he could not prove that the "trivial circle" was the only one. The Collatz assumption is the assumption in graph-theoretical formulation that Collatz graph of contiguous is. ${\displaystyle (1,4,2)}$ ${\displaystyle C}$

Principles

The path length (number of steps) depending on the starting numbers from 1 to 10,000.

For a trajectory as a sequence of numbers, one can distinguish three mutually exclusive cases: ${\displaystyle C}$

• the sequence ends in the (1,4,2) -cycle,
• the sequence grows beyond all borders,
• the result gets into a different cycle.

The presumption is that only the first case will occur, but neither the second nor the third case has yet been ruled out. It is also not known whether there can only be a finite number of cycles.

Since odd is always even, and thus the following iteration is always division by 2, the somewhat easier-to-use function is usually used instead of the Collatz function ${\displaystyle 3n+1}$ ${\displaystyle n}$ ${\displaystyle C}$

${\displaystyle T\colon \mathbb {N} \to \mathbb {N} ,\quad T(n)={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\(3n+1)/2&{\text{wenn }}n{\text{ ungerade ist,}}\end{cases}}}$     (Follow A014682 in OEIS )

is used, which makes two iterations at once for an odd number of times and reduces the cycle from (1,4,2) to (1,2) , which is assumed to be always achieved. The fold figure forms on and on from, in particular, there are initial values for any arbitrarily large factor that the repeated imaging with or increased by at least this factor. The Collatz conjecture is to believe that is equivalent for all integers is an integer with there. Terras showed in 1976 that the asymptotic density of the integers for which this is true exists and is equal to 1. ${\displaystyle n}$ ${\displaystyle C}$ ${\displaystyle k}$ ${\displaystyle T^{k}}$ ${\displaystyle 2^{k}m}$ ${\displaystyle m}$ ${\displaystyle 2^{k}m-1}$ ${\displaystyle 3^{k}m-1}$ ${\displaystyle C}$ ${\displaystyle T}$ ${\displaystyle n>1}$ ${\displaystyle k>0}$ ${\displaystyle T^{k}(n)<n}$ ${\displaystyle n>1}$

Calculations with computers showed:

• All positive whole numbers up to 2 ⁶⁸ (approx. 2.95 × 10 ²⁰ ) as starting values ​​confirm the assumption (as of July 2020).
• A cycle of the iteration other than (1,2) would have to consist of at least 10,439,860,591 numbers, of which at least 6,586,818,670 are odd numbers. ${\displaystyle T}$
• An infinite number of positive integers requires at least 6,143 log n iterations to reach 1. Stochastic models predict that on average (2 / log (4/3)) log n ≈ 6.952 log n steps are required and that at least as many iterations are required for at least half of all numbers . ${\displaystyle n}$ ${\displaystyle T}$ ${\displaystyle T}$
• For sufficiently large , the number of positive whole numbers that confirm the assumption as a starting value is at least equal to or less . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X^{0{,}84}}$

Terence Tao showed in 2019 that the Collatz conjecture “almost” applies to “almost all” natural numbers (that is, one ends with the Collatz sequence “near” 1, where the limit for proximity depends on the starting value N). For example, it follows from Tao's theorem that at least 99 percent of the natural numbers up to , with which one starts the Collatz sequence, reach an end value that is below 200. Tao used methods that he previously applied in the theory of partial differential equations, in which he statistically sampled a selection of initial values ​​and then examined the "long-term behavior" of the ensemble under the Collatz transformation. ${\displaystyle 10^{24}}$

Generalizations

For the Collatz problem, which is expanded to include all integers as starting values, there are at least four other cycles in addition to the (1,4,2) cycle:

• (0),
• (−1, −2),
• (−5, −14, −7, −20, −10) and
• (−17, −50, −25, −74, −37, −110, −55, −164, −82, −41, −122, −61, −182, −91, −272, −136, - 68, −34).

The last three cycles with positive instead of negative signs also arise with the definition instead of for odd . All values with end in one of the known cycles. ${\displaystyle C(n)=3n-1}$ ${\displaystyle C(n)=3n+1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle |n|<10^{8}}$

Marc Chamberland defined a continuous function which extends the discrete Collatz sequence to the range of real numbers. Simon Letherman, Dierk Schleicher and Reg Wood saw functions in the area of ​​complex numbers as an extension. General assumption: for odd always ends in and has only this one cycle. ${\displaystyle C(n)=3n+3^{x}}$ ${\displaystyle n}$ ${\displaystyle (4\cdot 3^{x},2\cdot 3^{x},1\cdot 3^{x})}$

If one considers the analog (5n + 1) problem, stochastic models deliver a completely different behavior: Almost all iterates diverge, which is confirmed by computer simulation. But it is an open problem to prove that only one orbit of the (5n + 1) problem actually diverges.

In 1972, John Conway looked at generalized (3n + 1) sequences and showed that they can simulate universal Turing machines ( generalized by him in the FRACTRAN programming language ). He also showed that a certain decision problem that asks whether an input value for the iteration that is a power of 2 leads to an iterated value that is also a power of 2 is unsolvable (the Collatz problem can also be formulate in such a way that for any natural numbers as input the iterate finally leads to a power of 2).

In their work published in 2020, Sultanow, Koch and Cox analyze the Collatz problem from a graph-theoretical perspective. You consider cycles for and the generalized form , being . The document contains a list of known cycles and derives conditions for their occurrence in Collatz sequences. ${\displaystyle 3n+1}$ ${\displaystyle kn+1}$ ${\displaystyle k\in \mathbb {N} _{>0}}$

literature

• Jeffrey C. Lagarias : The 3x + 1 problem and its generalizations , The American Mathematical Monthly 92, January 1985, pp. 3–23 (English; awarded the Lester R. Ford Prize in 1986 ; at MathDL ; at the CECM ; Zentralblatt review )
• Günther J. Wirsching: The dynamical system generated by the 3n + 1 function , Springer-Verlag, Berlin 1998, ISBN 3-540-63970-5 (English; revised version of the 1996 habilitation thesis; Zentralblatt review )
• Richard K. Guy : E16. The 3x + 1 problem and E17. Permutation sequences in Unsolved problems in number theory (3rd edition), Springer-Verlag, New York 2004, ISBN 0-387-20860-7 , pp. 330–336 and pp. 336–337 (English; Zentralblatt review )
• Jeffrey C. Lagarias: The 3x + 1 problem: An annotated bibliography (1963–1999) (sorted by author) , arxiv : math / 0309224 [math.NT], 2003–2011 (English)
• Jeffrey C. Lagarias: The 3x + 1 problem: An annotated bibliography, II (2000–2009) , arxiv : math / 0608208 [math.NT], 2006–2012 (English)
• Jeffrey C. Lagarias (Ed.): The ultimate challenge: The 3x + 1 problem , American Mathematical Society, Providence RI 2010, ISBN 978-0-8218-4940-8 (English; Zentralblatt review )
  • therein Jeffrey C. Lagarias: The 3x + 1 problem: An overview (PDF, 518 kB, book preview), pp. 3–29 (English)

Web links

Wikibooks: Collatz Sequences and Chessboard  - Learning and Teaching Materials

Commons : Collatz problem  - collection of images, videos and audio files

• Eric W. Weisstein : Collatz Problem . In: MathWorld (English).
• On the 3x + 1 problem by Eric Roosendaal, a distributed computing project that deals with the Collatz problem
• Collatz Conjecture by Jon Sonntag, a BOINC- based project that deals with the search for counterexamples (English; see Collatz Conjecture )
• The Collatz problem by Jürgen Dankert - Interactive script for the (3n + 1) - and (3n − 1) problem to generate sequences with arbitrarily large starting numbers
• Terence Tao : The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 , August 25, 2011
• Paul J. Andaloro: The 3x + 1 problem and directed graphs (PDF; 3.8 MB), Fibonacci Quarterly 40, 2002 (English)

Individual evidence

1. ↑ ^{a b} Lagarias : The 3x + 1 problem: An overview , 2010, p. 16 “Mathematics is not yet ready for such problems.” And p. 24 “Hopeless. Absolutely hopeless. " (English)
2. ↑ ^{a b} H. SM Coxeter : Cyclic sequences and frieze patterns: The fourth Felix Behrend memorial lecture , Vinculum 8, 1971, pp. 4-7 (English); Reprint with commentary in Lagarias (Ed.): The ultimate challenge: The 3x + 1 problem , 2010, pp. 211–218 (assumption on p. 214 ; Zentralblatt review )
3. ^ PHS: The Times Diary. Sums of money , The Times 61228, Jul 17, 1982, p. 8 and The Times Diary. Aftermath , The Times 61320, Aug. 25, 1982, p. 8
4. ↑ ^{a b} C. Williams, B. Thwaites, A. van der Poorten , W. Edwards, L. Williams: Ulam's conjecture continued again , PPC Calculator Journal 9, September 1982, pp. 23-24 (English)
5. ↑ Bryan Thwaites: Two conjectures, or how to win £ 1100 , The Mathematical Gazette 80, March 1996, pp. 35–36 (English)
6. ↑ ^{a b} Bryan Thwaites: Try to Win on nrich, March 10, 1998 (English)
7. ↑ Lagarias : The 3x + 1 problem and its generalizations , 1985, p. 4 (English)
8. ↑ ^{a b} Richard K. Guy : Don't try to solve these problems! American Mathematical Monthly 90, 1983, pp. 35-41 (English; Zentralblatt review ); Reprinted in Lagarias (ed.): The ultimate challenge: The 3x + 1 problem , 2010, pp. 231-239
9. ↑ Darren Glass: MAA Review zu Lagarias (ed.): The ultimate challenge: The 3x + 1 problem , 2010, MathDL, March 31, 2011 (English)
10. ↑ ^{a b} Lagarias : The 3x + 1 problem: An overview , 2010, p. 5 (English).
11. ↑ ITEM 133 (Schroeppel, Gosper, Henneman & Banks) from M. Beeler, RW Gosper , R. Schroeppel : HAKMEM , MIT AI Memo 239, February 29, 1972 (English).
12. ^ Martin Gardner : Mathematical Games , Scientific American 226, June 1972, pp. 114-118 (English); Reprinted with commentary in Wheels, life, and other mathematical amusements , WH Freeman and Company, New York 1983, ISBN 0-7167-1588-0 , pp. 196-197 and 203-204.
13. ^ ^{A b} J. H. Conway : Unpredictable Iterations in: Proceedings of the 1972 Number Theory Conference. University of Colorado, Boulder, Colorado , 1972, pp. 49-52 (English; Zentralblatt review ); Reprinted in Lagarias (ed.): The ultimate challenge: The 3x + 1 problem , 2010, pp. 219-223.
14. ↑ ^{a b} Riho Terras: A stopping time problem on the positive integers (PDF, 632 kB; October 24, 1974), Acta Arithmetica 30, 1976, pp. 241-252 (English; Zentralblatt review ) on
    this Riho Terras: On the existence of a density (PDF, 132 kB; July 27, 1978), Acta Arithmetica 35, 1979, pp. 101-102 (English; Zentralblatt review ).
15. ↑ Lagarias : The 3x + 1 problem and its generalizations , 1985 (English).
16. ↑ Lagarias : The 3x + 1 problem and its generalizations , 1985, p. 3 (English).
17. ↑ Guy : E17. Permutation sequences , 2004 (English).
18. ^ Bryan Thwaites: My conjecture , Bulletin of The Institute of Mathematics and its Applications 21, March / April 1985, pp. 35-41 (English; Zentralblatt review ).
19. ↑ Lothar Collatz : On the Origin of the (3n + 1) Problem , Journal of Qufu Normal University Natural Science Edition 12 No. 3, 1986, pp. 9-11 (Chinese translation from the German by Zhi-Ping Ren); On the motivation and origin of the (3n + 1) problem in Lagarias (ed.): The ultimate challenge: The 3x + 1 problem , 2010, pp. 241–247 (English translation from Chinese).
20. ^ Douglas R. Hofstadter : Gödel, Escher, Bach: an Eternal Golden Braid , Basic Books, New York 1979, ISBN 0-465-02685-0 , pp. 400-402 (English).
21. ^ Brian Hayes: Computer recreations: On the ups and downs of hailstone numbers (PDF; 1.1 MB), Scientific American 250, January 1984, pp. 10-16 (English).
22. ↑ Günther J. Wirsching: About the 3n + 1 problem , Elements of Mathematics 55, November 2000, pp. 142–155 ( Zentralblatt review )
23. ↑ Lagarias : The 3x + 1 problem: An overview , 2010, p. 22 (English).
24. ↑ Lagarias : The 3x + 1 problem: An overview , 2010, pp. 16-17 (English).
25. ↑ Eric Roosendaal: On the 3x + 1 problem. In: EricR.nl. July 20, 2020, accessed on July 27, 2020 . 
26. ↑ Shalom Eliahou: The 3x + 1 problem: new lower bounds on nontrivial cycle lengths , Discrete Mathematics 118, August 1993, pp. 45–56 (English; result using the validity of the conjecture up to 20 × 2 ⁵⁸ ; Zentralblatt review ) .
27. ^ David Applegate , Jeffrey C. Lagarias : Lower bounds for the total stopping time of 3x + 1 iterates , Mathematics of Computation 72, April 2003, pp. 1035-1049 (English; Zentralblatt review ).
28. ↑ Ilia Krasikov, Jeffrey C. Lagarias : Bounds for the 3x + 1 problem using difference inequalities , Acta Arithmetica 109, 2003, pp. 237-258 (English; Zentralblatt review ).
29. ↑ Kevin Hartnett: Mathematician proves huge result on 'dangerous' problem , Quanta Magazine, December 11, 2019 (English).
30. ↑ Terence Tao : Almost all orbits of the Collatz map attain almost bounded values , arxiv : 1909.03562 , September 2019 (English).
31. ↑ Guy : E16. The 3x + 1 problem , 2004, p. 332 (English)
32. ↑ Marc Chamberland: A continuous extension of the 3x + 1 problem to the real line (PDF; 159 kB), Dynamics of continuous, discrete and impulsive dynamical systems 2, 1996, pp. 495–509 (English; Zentralblatt review )
33. ↑ Simon Letherman, Dierk Schleicher , Reg Wood: The 3n + 1-problem and holomorphic dynamics , Experimental Mathematics 8, 1999, pp. 241-251 (English)
34. ↑ Lagarias : The 3x + 1 problem: An overview , 2010, p. 11 and p. 22
35. ↑ Eldar Sultanow, Christian Koch, Sean Cox: Collatz Sequences in the Light of Graph Theory. (PDF, 1148 kB) University of Potsdam 2020.