Nov 21, 2020

# 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/