Mathematik | Informatik
Mahilan Sritharan, 2004 | Grenchen, SO
This project presents an in-depth analysis of the Collatz Conjecture, exploring its mathematical properties and examining the behavior of associated sequences. The reversibility of the whole Collatz iteration procedure including terminating cycle {16, 8, 4, 2, 1} was used for a computational approach to construct the Collatz graph. The paper investigates the behavior of iteration maps similar to the Collatz function, such as 3n+1, and 5n+1. Additionally, the concept of algorithmic decidability and the potential undecidability of the Collatz Conjecture was considered, drawing parallels with other unsolved problems such as the Halting problem. The paper also addresses the challenges inherent to the conjecture, such as the difficulty of it to prove for all natural numbers. It concludes with the imaginable steps to advance towards a resolution of the Collatz problem.
Introduction
The Collatz Conjecture was published by Lothar Collatz in 1937. It involves building a sequence by taking any positive integer and applying two rules: If the number is odd, the number is multiplied by three and one is added. If even, the number is divided by two. Collatz’s conjecture is that no matter which positive integer we start with, the sequence will always reach the cycle of 4, 2, 1, and then repeat infinitely. But despite its apparent simplicity the conjecture has not been confirmed true for all natural numbers. We are examining why a proof for the Collatz problem has not been found yet and what separates what is proven from what is still unsolved.
Methods
In the project, a Collatz graph was created to show the interconnection between the sequences formed by the starting numbers. Moreover, the project examines different mathematical approaches, such as Terence Tao’s partial proof, in addressing the Collatz problem to answer the guiding question and speculating on its decidability. The analysis of potential loop formations focused on investigating the loop formation in 3n-1 and 5n+1 sequences and comparing it to the initial 3n+1 sequence.
Results
An analysis exploring the distribution of even and odd numbers within Collatz sequences has uncovered that the ratio of even to odd numbers tends to converge towards a 2:1 ratio. In comparing the sequences generated by 3n+1, 3n-1, and 5n+1, it was observed that sequences produced by 3n-1 and 5n+1 form extra loops, while sequences generated by 3n+1 lack these additional loops. Further investigation has shown that approximately two-thirds of starting values for 3n-1 become trapped in loops distinct from the standard cycle observed in the Collatz function. Furthermore, comparisons regarding decidability have not revealed any arguments that the Collatz problem is algorithmically undecidable. It is assumed that the Collatz conjecture will be considered solvable until a significant case arises in which it appears algorithmically undecidable.
Discussion
This disparity between 3n-1 and 3n+1 suggests a potentially major dynamic difference in the behavior of these two seemingly similar functions, particularly regarding loop formation within their respective sequences. Examining functions of the form f(n) = kn + s, where k and s take specific values (natural numbers), could offer valuable insights. However, it is essential to acknowledge that advancing beyond probability techniques is necessary to potentially resolve the Collatz problem. This requires a broader thinking and perhaps the exploration of entirely new methods.
Conclusions
On the way to find a complete proof to the Collatz problem, partial proofs (true for almost all numbers) could unfold other ideas. Creating an idea in proving that nearly every Collatz function converges to one specific finite number, holds promise. It is worth nothing that Tao’s partial proof and his techniques cannot be applied here (Tao himself acknowledges that), as Tao’s partial proof does not directly concern specific numbers within the Collatz sequence. However, such an approach must certainly address this aspect. What is indisputable is that the Collatz problem requires a completely new idea or technique. Such progress would bring us closer to establishing that all starting numbers ultimately lead to one.
Würdigung durch den Experten
Philémon Bordereau
The Collatz problem is all but a simple problem. The formulation might be understandable by a kid, but no mathematician has yet come close to solving it. It is already challenging to realize where the difficulties lie and where the complex mathematical dynamics hide. In that sense, this project represents a compelling outline of the main characteristics of the problem, together with the ideas and obstructions that mathematicians established. The effort to design computer-assisted visual representations and numerical simulations is to be acknowledged.
Prädikat:
gut
Kantonsschule Solothurn
Lehrer: Cédric Schärer
