The Collatz Conjecture
Collatz’s conjecture is the simplest unsolved math problem in history.
Take any number n.
- If n is even, divide by 2
- If n is odd, calculate 3 * n + 1
And keep doing this.
The conjecture says that the sequence will always converge to 1.
Example: initial number 5
5 -> 16 -> 8 -> 4 -> 2 -> 1
There were 5 steps to converge to 1.
Example: starting number 6
6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
There were 8 steps to converge to 1.
For numbers from 2 to 50, the result of the number of steps shows:
Interesting information: although extremely simple to formulate, this conjecture has not yet been proved.
It is counter intuitive; it looks like it will grow, but then it converges.
The sequence is erratic: a number may need 100 steps, the neighbor needs 5.
In VBA, the simplest way to solve is with a simple while loop.
Function collatz (n)
Dim count As Long
count = 0
While n> 1
If n Mod 2 = 0 Then
n = n / 2
Else
n = 3 * n + 1
End If
count = count + 1
Wend
collatz = count
End Function
It is possible to think of a more complex data structure, but with better computational performance.
For example, saving the number of steps for all values already run. Calculate the sequence until it reaches a lower number than the current one, and then retrieve the result already calculated from memory.
With this method, it is possible to calculate the first 110 thousand numbers, in less than 1 second.
In VBA, the limit is the maximum size of type Long. There is no Big Int type, as in Java or Python, which makes calculating more than that quite complicated.
Code on Github: https://github.com/asgunzi/CollatzVBA
See also:
https://en.wikipedia.org/wiki/Collatz_conjecture
https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/
