Start the sequence with any positive integer,
1. If the number is even, divide by 2
1. If the number is even, divide by 2
2. If the number is odd, triple and add 1
Stop if the new number is one; if not, repeat the set of rules.
The sequences have been shown through numerical simulation to always reach 1 without a counterexample found. However, no one has proven that the sequence will always reach 1. Hence, this is a conjecture and not a proven theorem.
Additional Thoughts
While I don't have a contribution to add to a proof, I offer a probabilistic view of the sequence.
First, define Known Terminator as a number, that once reached, will bring the sequence to 1. Common known terminators are powers of 2, multiples of 5 and any number reached in a sequence that reaches 1 as an investigator explores different starting numbers.
Next, for a given starting number, No, or any number in a generated sequence, assume there is a 50%-50% probability of the number being even or odd. The next number, N1, in the series can be expressed algebraically on a probabilistic, expected-value basis:
N1 = 0.50 (No/2) + 0.50 (3No + 1) = 1/4 No + 3/2No + 1/2 = 7/4 No + 1/2
An alternate formulation of rule 2 is:
If the number is odd, triple and add 1, then divide by 2 (so stated because because it is guaranteed that if N is odd, 3N + 1 is even).
With the alternate formulation, the new expected value of N1 becomes:
N1 = 0.50 (No/2) + 0.50 (1/2)(3No + 1) = 1/4 No + 3/4No + 1/4 = No + 1/4
Since both terms, 7/4 No + 1/2 and No + 1/4, are greater than No, we can now state, on an expected value basis, the sequence tends to increase until reaching a known terminator.
For anyone who has explored the conjecture, this is stating the obvious, but I wanted to share in case it inspires some additional progress. I'll be challenging my fellow Collatz fans, Andrew Marshall and Sandra Perez, to contribute their thoughts.
In the news:
Recent Popular Mechanics article - Collatz
Update August 26, 2020 - Collatz article in Quanta Magazine
Another article sharing the probalistic approach of my post: https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/
It's interesting that although I'm a fan of Collatz, I look at it from a different perspective to you. You view it as a mathematician does, while I view it as a code monkey does. I only ever (naively) considered that I might find the counterexample using a bit of code and some computing power without ever considering proving it. However, unsuccessfully trying to find that counterexample taught me some important lessons, such as an appreciation for large numbers, and how humans are simply not wired to comprehend them.
ReplyDeleteAnother recent article referenced. I liked that it came with warnings "do not attempt - you will get trapped."
Deletehttps://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/
ReplyDelete