The Collatz Conjecture

OldTrout, Going Postal

OldTrout, Going Postal

This is also known as the ‘half or triple plus one’ problem.

Let \(n\) be any arbitrary positive integer.

If \(n\) is even, then divide it by two.

Otherwise, if \(n\) is odd, then multiply it by three and add one.

We have the piecewise function :

\(
f(n) =
\begin{cases}
n/2, & \text{if n is even}\\
3n + 1, & \text{if n is odd}
\end{cases}
\)

Now iterate these steps to form a sequence.

The Collatz conjecture states that the sequence will eventually reach the number one for all \(n\).

Like many open conjectures in arithmetic (number theory) it is easily understood but very difficult to prove.

The first ten sequences :

\( n = 1 : 1, 4, 2, 1.\\
n = 2 : 2, 1.\\
n = 3 : 3, 10, 5, 16, 8, 4, 2, 1.\\
n = 4 : 4, 2, 1.\\
n = 5 : 5, 16, 8, 4, 2, 1.\\
n = 6 : 6, 3, 10, 5, 16, 8, 4, 2, 1.\\
n = 7 : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.\\
n = 8 : 8, 4, 2, 1.\\
n = 9 : 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.\\
n = 10 : 10, 5, 16, 8, 4, 2, 1.\\
\)

These sequences are often referred to as the hailstone numbers because they rise and fall before eventually dropping down to one.

The sequence for \(n = 27\) takes \(111\) steps rising to \(9,232\) before falling to \(1\).

OldTrout, Going Postal

All positive integers up to \(2^{64}\)  have been tested and no counter-example has been found, however, this does not constitute a proof.

We can look at the conjecture extended over the complex plane and see the fractal generated by the iterations.  The Collatz function over the real numbers is defined as :

\( f(x) = \bigl(1 + (-1)^x\bigr) \frac{x}{4} + \bigl(1 \, – (-1)^x \bigr) \frac{3x +1}{2} \)

Over the complex plane it is defined as :

\( f(z) = \frac{1}{4} \bigl(2 + 7z \, – (2 + 5z)\cos(\pi z) \bigr) \)

since \((-1)^x = \cos(nx)\).

The Collatz \(f(z)\) fractal :

OldTrout, Going Postal

The large black region is around \(z = 0\).  The spikes to the left and right are \(z = -2, -1, 1\) and \(1\).

Nathaniel Johnston introduces a modified Collatz function :

\(g(z) = \frac{z}{4} \bigl(1 + \cos(\pi z) \bigr) + \bigl(\frac{3z + 1}{16} \bigr) \bigl(1 \, – \cos(\pi z) \bigr) \bigl(3 \,- \sqrt2\cos \bigl((2z \, -1)\frac{\pi}{4} \bigr) \bigr) \)

His reason for doing so being that \(g(1) = 1\).  That is, \(1\) is a fixed point of \(g(z)\).

The Collatz \(g(z)\) fractal :

OldTrout, Going Postal

Close-up of the \(g(z)\) fractal at \(z = 1\) :

OldTrout, Going Postal

\(g(z)\) at \(z = 4\) :

OldTrout, Going Postal

\(g(z)\) at \(z = 8\) :

OldTrout, Going Postal

\(g(z)\) at \(z = 16\) :

OldTrout, Going Postal

\(g(z)\)  at \(z = -8\) :

OldTrout, Going Postal
 

© OldTrout \(2018\)