Simeon Nikulin – 2022 Teddy Rocks Maths Essay Competition Commended Entry

Pick any positive integer, for example, 5. Then apply two simple rules. If the number is odd, multiply it by 3 and add 1. For example, 5 multiplied by 3 is 15 and added with 1 is 16. If the number is even, divide it by 2. For example, 16 is an even number so 16 divided by 2 is 8. Continue applying these two rules. 8 is an even number so 8 divided by 2 is 4 and then 2 and then 1. 1 is an odd number so 1 multiplied by 3 is 3 and added with 1 is 4. But 4 transforms into 2 and then into 1. This sequence has fallen into a repeating, four-two-one cycle.

This is known as the Collatz Conjecture. The conjecture questions whether performing two fixed arithmetic operations repeatedly on any integer will cause it to eventually transform into the number 1, and afterwards continue repeating in a four-two-one cycle.  Despite being introduced in 1937 by the German mathematician Lothar Collatz, after whom it was named, no definite proof has been produced for the conjecture 85 years later.  Both professional and amateur mathematicians are told not to misspend time attempting to solve it, and in the words of the highly accredited and world renowned mathematician Terence Tao, “the Collatz Conjecture is one of the most elementary unsolved problems in mathematics.”  

When discussing the conjecture, mathematicians use specific terminology which originates from aviation. Consider the sequence for the integer five:

5 → 16 → 8 → 4 → 2 → 1…

The flight number is the initial starting integer, which is 5. The altitudes are the individual integers that the sequence contains. For the flight number 5, there would be six altitudes: 5, 16, 8, 4, 2 and 1. These numbers together make up the trajectory, which is formed by the different altitudes that a sequence contains.  The stopping distance is the number of different altitudes, or steps, that it takes for the flight number to reach 1.

Finding a solution for such a conjecture begins with a heuristic overview. An observation of the two rules that govern the conjecture reveals that they are misleading. Since there is an identical number of odd and even numbers and odd numbers are tripled and even numbers are only halved, then a reasonable assumption can be made that the trajectory should increase. But, when an odd number is multiplied by 3 and added with 1, the result will always be an even number. Then, as the rules dictate, the number must be divided by two. This means that the following arithmetic operation is performed on odd numbers:

For large numbers, the addition of 1 has a negligible effect, which means that the maximum odd numbers can increase by is .

Consider the trajectory from one odd number to the next. Multiplying an odd number by 3 and adding one results in an even number.  One half of the numbers are only divisible by 2, which is equal to 2¹, and therefore can only be halved once until there is an odd number. One fourth of the numbers are divisible by 4, which is equal to 2², and therefore they can be halved twice. One eighth of the numbers are divisible by 8, which is equal to 2³, and therefore they can be halved thrice.  One sixteenth of the numbers are divisible by 16, which is equal to 2⁴, and therefore they can be halved fourthold.

The geometric average, which is the middle number between two terms in a geometric sequence, of the ratios of the outcomes is  .

This indicates that on average the trajectory reduces its altitude by 25% when moving from one odd number to the next, which is an argument in support of the conjecture as the trajectory should decrease to 1.

A closer inspection of the leading digits of altitudes in a trajectory reveals another pattern.  Using Python, a computer programming language favoured by scientists and mathematicians, to count the number of occurrences of a leading digit in all of the altitudes of the trajectories of all of the flight numbers from one to one million, a histogram is formed.

The distribution shown in the histogram is obedient to Benford’s Law. Benford’s Law predicts the distribution of leading digits in sets of numerical data, with the leading digit ‘1’ appearing approximately 30% of the time, while the leading digit ‘9’ appears approximately less than 5% of the time, which is the case in the histogram. While this does not contribute significantly to a solution, it does demonstrate that a graphical analysis of the conjecture does reveal behaviours and patterns that are difficult to uncover otherwise.

All of the trajectories in the conjecture are governed by two rules, which could mean that there is likely to be a certain pattern to the trajectories. The trajectories of the flight numbers one to one hundred can be displayed in a line graph.

The graph demonstrates that there is seemingly no pattern to the trajectories of flight numbers, besides all eventually transforming into the number one.  However, manipulation of this data does yield useful results.

Consider the random nine figure integer 658878298. Large numbers are effective in revealing patterns as they have many altitudes to show them distinctly on a graph. The trajectory of the number is standard, it reaches 1 after a while but the difference between the peak altitude and 1 is so great that the approach to 1 is concealed at this scale.

Plotting the logarithm of the trajectory of the number 658878298 produces a graph with a continuous downwards trend. This is known as geometric Brownian motion, a process in which the logarithm of randomly varying quantities reveals systematic tendencies of quantities to increase or decrease over a period of time. In finance, geometric Brownian motion is used to model stock prices and the behaviour of stock markets, which usually trend upwards over a period of time. The gradual decrease of the logarithm of the trajectory indicates that the altitudes also tend to decrease which supports the conjecture.

Another graph which is suitable for the representation of the Collatz conjecture is a directed graph. A directed graph is made up of vertices and arcs, which show the relationship between different quantities. The Collatz conjecture makes an assumption that all of the flight numbers transform into one, which means that in a directed graph they originate from the number 1.  This constructs a graph which resembles the flow of several tributaries into a river.  Altering the directed graph by rotating the vertices clockwise if the number is even and anti-clockwise if the number is odd produces a fascinating model.

In a 3 dimensional plane, the altered directed graph elegantly resembles a natural plant, which is a token to the role of mathematics in the patterns of nature.

The Collatz conjecture is difficult to prove true, and with many mathematicians attempting to find a solution without making significant progress encourages the possibility that the conjecture is false, and instead a counter example should be found.

There are two situations which could prove the conjecture false.  There could be another cycle, apart from the four-two-one cycle, which repeats indefinitely. This would cause the trajectory to never reach one and prove the conjecture false.

The other situation that would prove the conjecture false is if a flight number encounters a trajectory where the altitudes cause it to escalate to infinity. This would disprove the conjecture as the trajectory would never reach 1.

Discovering a number which would counter the conjecture would require examining a plethora of numbers, and this is only possible by automation.

Using computers running the 3x+1 algorithm, mathematicians have produced an argument for the conjecture using experimental evidence for all integers from 1 up to 2⁶⁸. This is approximately 295 quintillion numbers (2.95 x 10²⁰), none of which disproved the conjecture. This information is insufficient as a solution, as there could be a number larger than 295 quintillion which disproves the conjecture. This was the case in the Polya Conjecture, which argued that half or more of natural numbers have an odd number of prime factors, but was disproved by using an extremely large counter example of 1.845 x 10³⁶¹.

Ultimately, the Collatz conjecture is an infamously elementary but unsolved problem which tests the bounds of mathematics.  The contrast between the huge investment of resources and the absence of meaningful progress in trying to find a solution indicates that mathematics is unprepared to solve the conjecture, with renowned mathematician Paul Erdos agreeing that ‘’mathematics might not be ready for such problems.” Proving a false theorem is impossible and the struggle to find a solution has led to some mathematicians believing that the conjecture may be false. Whether the conjecture is proved or disproved in the future it will certainly be by a comprehensive analysis rather than the exhaustive examination of numbers using computers. The incentive of several large monetary prizes creates hope that the conjecture will one day be solved.

---

References

Python Programs: To collect data to be used for the various graphs in this essay three Python programs were written by the author. The Python programs and instructions on how to run them on Replit.com can be found in the Github repository: https://github.com/simeonikulin/Collatz-Conjecture-Programs

The Notorious Collatz Conjecture by Terence Tao

Almost All Orbits Of The Collatz Map Attain Almost Bounded Values by Terence Tao

The 3n+1 Conjecture: Behaviour of The Stopping Time Function

All diagrams, graphs and images, apart from the images of the plant and 3 dimensional directed graph, were made by the original author of this essay. The images found that were not made by the author of this essay required no attribution.