Collatz Conjecture Or The 3n + 1 Problem

featured image thumbnail for post Collatz Conjecture Or The 3n + 1 Problem

A conjecture, in Mathematics, is a conclusion or proposition that is considered to be true because of supporting evidence. But no definitive proof or disproof exists. This article will look at one such conjecture, the Collatz.

What is the Collatz conjecture?

Consider a sequence defined as follows:

  • Start with an arbitrary positive integer n
  • if n is even, then the next number will be half of it: n/2
  • if n is odd, then the next number will be one more than three times n: 3n + 1

The Collatz conjecture states that this sequence will eventually reach 1, no matter what number we started with.

A couple of examples will make this clearer.


Let’s start with 5.
Because 5 is odd, the next number will be

3∗5+1=15+1=163 * 5 + 1 = 15 + 1 = 16

16 is even, so the next number will be

162=8\frac{16}{2} = 8

The next numbers will be 4, 2, 1
The full sequence is: 5, 16, 8, 4, 2, 1

Let’s take another example.

Let’s start with 12 this time.
Because 12 is even, the next number will be

122=6\frac{12}{2} = 6

The next number will be

62=3\frac{6}{2} = 3

Followed by

3∗3+1=103 * 3 + 1 = 10

And then

102=5\frac{10}{2} = 5

and from this point on, the sequence follows the first example. Hence the full sequence is:

12,6,3,10,5,16,8,4,2,112, 6, 3, 10, 5, 16, 8, 4, 2, 1

So, both the sequences eventually reach 1.

Once the sequence reaches 1, continuing it results in the infinite loop:

1=>4=>2=>1.1 => 4 => 2 => 1.

The function f(n) which generates a Collatz sequence can formally be written as:

f(n)={n2(n mod 2)=03n+1(n mod 2)=1f(n)= \begin{array}{cc} \{ & \begin{array}{cc} \frac{n}{2} & (n \bmod 2)=0 \newline 3 n+1 & (n \bmod 2)=1 \newline \end{array} \end{array}

The operations performed on each number, halving if even, and tripling and adding one if odd, are called Collatz operations. The root of the sequence is its starting number. In the examples above, 5 and 12 are the roots. The numbers in a given sequence, as well as the sequence as a whole, are also called the orbits of the root.

Other Names for the Collatz conjecture

The Collatz conjecture has many other names: the Ulam conjecture, Kakutani’s problem, Thwaite’s conjecture, Hasse’s algorithm, Syracuse problem, and sometimes, just 3N + 1.

Hailstone Numbers

The numbers in a Collatz sequence are sometimes called hailstone numbers. This is because the numbers in the sequence tend to go both up and down, much like hailstones in a cloud. The figure below demonstrates this for the root 27.

picture0

Stopping Time and Total Stopping Time

Suppose a0 is the positive integer we start with and the sequence we get by repeatedly performing the Collatz operations is a(0), a(1), a(2), … and so on.

An={An−12(An mod 2)=03∗An−1(An mod 2)=1A_{n}= \begin{array}{cc} \{ & \begin{array}{cc} \frac{A_{n-1}}{2} & (A_n \bmod 2)=0 \newline 3 * A_{n-1} & (A_n \bmod 2)=1 \newline \end{array} \end{array}

The smallest sequence index i for which a(i) < a0 is called the stopping time for a0. If there is no such index i, the stopping time for a0 is said to be infinity.

Take the sequence for the number 5:

a(0)=5a(1)=16a(2)=8a(3)=4a(0) = 5 \newline a(1) = 16 \newline a(2) = 8 \newline a(3) = 4 \newline

Note that 4 < 5, (a(3) < a(0))
Hence, the stopping time for number 5 is i = 3.

The smallest sequence index k for which a(k) = 1 is called the total stopping time for a0. If there is no such index k, the total stopping time for a0 is said to be infinity.

Again, for the number 5:

a(0)=5a(1)=16a(2)=8a(3)=4a(4)=2a(5)=1a(0) = 5 \newline a(1) = 16 \newline a(2) = 8 \newline a(3) = 4 \newline a(4) = 2 \newline a(5) = 1 \newline

Hence, the total stopping time for number 5 is k = 5.

On looking at the orbits, it becomes plain that a power of 2 (i.e., 2n) must appear in the sequence for it to reduce to 1. Once a power of 2 appears, the halving operation is the only one that is performed, as every halving operation produces an even number till 1 is reached. In the sequences above,16 is the power of 2, which eventually leads the sequence to 1.

No obvious connection has been observed between the starting number and the total stopping time. The total stopping time for 26 is 10, but that for 27 is 111.

picture1

The graph above shows a plot of the total stopping times (x-axis) and the number of occurrences (y-axis) for all numbers from 1 to 100 million.

picture2

The figure above shows all roots which have a total stopping time of less than 20. All paths converge at 1, which is at the center of the circle.

Cycle length

In the Collatz sequences for positive integers, once we reach the value 1, we get a cycle where sequence elements keep taking the value 1 periodically.

Suppose a(k) = 1:

a(k)=1=>a(k+1)=3∗a(k)+1=4=>a(k+2)=a(k+1)2=2=>a(k+3)=a(k+2)2=1a(k) = 1 \newline => a(k+1) = 3*a(k)+1 = 4 \newline => a(k+2) = \frac{a(k+1)}{2} = 2 \newline => a(k+3) = \frac{a(k+2)}{2} = 1 \newline

Hence

1=>4=>2=>1=>4=>2=>…1 => 4 => 2 => 1 => 4 => 2 => …

Since the value 1 recurs once every 3 elements, we say that the cycle length or cycle period is 3.

Extended or Generalized Collatz conjecture

So far, we have only looked at Collatz sequences starting with positive integers. The Collatz conjecture has been extended to all integers (including zero and negative integers) and all rational numbers with odd denominators. In these cases, the Collatz sequence does not always reach the value 1. But the sequence will always reach a cycle that then keeps repeating.

Zero

Consider a(k) = 0:

a(k)=0 :even=>a(k+1)=a(k)2=0 :even a(k) = 0 \ :even \newline => a(k+1) = \frac{a(k)}{2} = 0 \ :even

Cycle of length 1.

Note that, for integers, the only way to reach this cycle is to start the sequence with a(0) = 0.

Negative integers

The extended conjecture states that for all negative integers, the Collatz sequences will eventually reach one of the three cycles described below.

Cycle 1

a(k)=−1:odd=>a(k+1)=3∗a(k)+1=−2:even=>a(k+2)=a(k+1)2=−1:odda(k) = -1 :odd \newline => a(k+1) = 3*a(k)+1 = -2 :even \newline => a(k+2) = \frac{a(k+1)}{2} = -1 :odd \newline

Cycle of length 2.

Cycle 2

a(k)=−5:odd=>a(k+1)=3∗a(k)+1=−14:even=>a(k+2)=a(k+1)2=−7:odd=>a(k+3)=3∗a(k+2)+1=−20:even=>a(k+4)=a(k+3)2=−10:even=>a(k+5)=a(k+4)2=−5:odda(k) = -5 : odd \newline => a(k+1) = 3*a(k)+1 = -14 : even \newline => a(k+2) = \frac{a(k+1)}{2} = -7 : odd \newline => a(k+3) = 3*a(k+2) +1 = -20 : even \newline => a(k+4) = \frac{a(k+3)}{2} = -10 : even \newline => a(k+5) = \frac{a(k+4)}{2} = -5 : odd \newline

Cycle of length 5.

Cycle 3

a(k)=−17:odd=>a(k+1)=3∗a(k)+1=−50:even=>a(k+2)=a(k+1)2=−25:odd=>a(k+3)=3∗a(k+2)+1=−74:even=>a(k+4)=a(k+3)2=−37:odd=>a(k+5)=3∗a(k+4)+1=−110:even=>a(k+6)=a(k+5)2=−55:odd=>a(k+7)=3∗a(k+6)+1=−164:even=>a(k+8)=a(k+7)2=−82:even=>a(k+9)=a(k+8)2=−41:odd=>a(k+10)=3∗a(k+9)+1=−122:even=>a(k+11)=a(k+10)2=−61:odd=>a(k+12)=3∗a(k+11)+1=−182:even=>a(k+13)=a(k+12)2=−91:odd=>a(k+14)=3∗a(k+13)+1=−272:even=>a(k+15)=a(k+14)2=−136:even=>a(k+16)=a(k+15)2=−68:even=>a(k+17)=a(k+16)2=−34:even=>a(k+18)=a(k+17)2=−17:odda(k) = -17 : odd \newline => a(k+1) = 3*a(k)+1 = -50 : even \newline => a(k+2) = \frac{a(k+1)}{2} = -25 : odd \newline => a(k+3) = 3*a(k+2) +1 = -74 : even \newline => a(k+4) = \frac{a(k+3)}{2} = -37 : odd \newline => a(k+5) = 3*a(k+4) +1 = -110 : even \newline => a(k+6) = \frac{a(k+5)}{2} = -55 : odd \newline => a(k+7) = 3*a(k+6) +1 = -164 : even \newline => a(k+8) = \frac{a(k+7)}{2} = -82 : even \newline => a(k+9) = \frac{a(k+8)}{2} = -41 : odd \newline => a(k+10) = 3*a(k+9) +1 = -122 : even \newline => a(k+11) = \frac{a(k+10)}{2} = -61 : odd \newline => a(k+12) = 3*a(k+11) +1 = -182 : even \newline => a(k+13) = \frac{a(k+12)}{2} = -91 : odd \newline => a(k+14) = 3*a(k+13) +1 = -272 : even \newline => a(k+15) = \frac{a(k+14)}{2} = -136 : even \newline => a(k+16) = \frac{a(k+15)}{2}= -68 : even \newline => a(k+17) = \frac{a(k+16)}{2} = -34 : even \newline => a(k+18) = \frac{a(k+17)}{2} = -17 : odd \newline

Cycle of length 18.

Rational numbers with odd denominators

Rational numbers with odd denominators are considered to be odd or even when their numerators are odd or even respectively in the simplest form.

There seem to be many more possible cycles for rational numbers with odd denominators. But the Collatz sequences for these numbers also reach a cycle.

Let’s look at some examples.

  1. a(0) = ⅓
a(0)=⅓:odd=>a(1)=3∗a(0)+1=2:even=>a(2)=a(1)2=1:odda(0) = ⅓ : odd \newline => a(1) = 3*a(0)+1 = 2 : even \newline => a(2) = \frac{a(1)}{2} = 1 : odd \newline

… and we get a cycle 1 => 4 => 2 => 1 ... of length 3.

  1. a(0) = ⅕
a(0)=⅕:odd=>a(1)=3∗a(0)+1=⁸⁄₅:even=>a(2)=a(1)2=⅘:even=>a(3)=a(2)2=⅖:even=>a(4)=a(3)2=⅕:odda(0) = ⅕ : odd \newline => a(1) = 3*a(0)+1 = ⁸⁄₅ : even \newline => a(2) = \frac{a(1)}{2} = ⅘ : even \newline => a(3) = \frac{a(2)}{2} = ⅖ : even \newline => a(4) = \frac{a(3)}{2} = ⅕ : odd \newline

… and we get a cycle ⅕ => ⁸⁄₅ => ⅘ => ⅖ => ⅕ … of length 4.

  1. a(0) = -⅓
a(0)=−⅓:odd=>a(1)=3∗a(0)+1=0:evena(0) = -⅓ : odd \newline => a(1) = 3*a(0)+1 = 0 : even \newline

c. … and we get a cycle 0 -> 0 … of length 1.

The current state of the conjecture

The Collatz conjecture has not been proved to be true for all positive integers. However, it has been verified for every number till 268. It is comparatively easy to prove for a given number. But it is a lot more difficult to prove for all numbers.

In 1976 Riho Terras showed that, after repeated application of the Collatz function, for almost all numbers the Collatz sequence for n ends up less than n. Showing that the numbers in the sequence consistently get smaller is one path to showing that they eventually get to 1.

In 2019, Terence Tao, one of the world’s greatest living mathematicians, improved on this result. Tao proved that for almost all numbers the Collatz sequence for n ends up much lower than n: below ⁿ⁄₂, below n1/2, or below ln(n) (the natural log of n). So, for almost every number, we can guarantee that its Collatz sequence goes as low as we want.

picture3

The conjecture is easy to understand but difficult to prove (the word "diabolical" is often used to describe the problem). One mathematician said, "Mathematics is not yet ready for such problems". Another mathematician, Jeffrey Lagarias, the greatest living authority on the conjecture, has said, "This is an extraordinarily difficult problem, completely out of reach of present-day mathematics".

What is so intriguing about the Collatz conjecture is its simplicity. Anyone can start playing with it and take a shot at proving or disproving it. It is also incredibly addictive. No wonder Lagarias routinely advises young mathematicians against working on the conjecture at the start of their careers.

The Collatz conjecture is possibly the simplest, unsolved problem in mathematics. It has not been possible to solve it with the mathematical theories known today. So, mathematicians must develop new theories to prove or disprove it. Therein lies the importance of this conjecture.

About Lothar Collatz

picture4

Lothar Collatz (1910 - 1990), a German mathematician and academician, proposed the Collatz conjecture in 1937. Professor Collatz made many seminal contributions to mathematics, yet he is most famous for having proposed the conjecture which bears his name. It is said of him, "Professor Collatz was a truly wonderful individual. He was modest in his behavior, and ever amiable and helpful."

What’s New With Java 17

What’s New With Java 17

The Best 6 Opening Chess Moves

The Best 6 Opening Chess Moves

A Look At Alternatives to Docker

A Look At Alternatives to Docker

Ulad Kaminski