Tag: Functions

There are infinite numbers between 0 and 1. There’s 0.1 and 0.12 and 0.112 and an infinite collection of others. Of course, there is a bigger infinite set of numbers between 0 and 2, or between 0 and a million. Some infinities are bigger than other infinities… I cannot tell you how grateful I am for our little infinity. You gave me forever within the numbered days, and I’m grateful.

John Green

Glad you came by. I wanted to let you know I appreciate your spending time here at the blog very much. I do appreciate your taking time out of your busy schedule to check out Math1089!

One of the most interesting features of mathematics is that it is possible to phrase problems in a few lines that turn out to be incredibly hard. The Collatz Conjecture is one such, was proposed in 1937 by German mathematician Lothar Collatz.

It is also known as the 3n + 1 problem (or the 3n + 1 conjecture), the Ulam conjecture (after Stanisław Ulam), Kakutani’s problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse’s algorithm (after Helmut Hasse), or the Syracuse problem.

Though the conjecture is still unsolved, but the problem on which the conjecture is built is remarkably simple. Take any natural number. To get the next number, there is a rule, or function. We then apply that rule over and over, and see where it takes us. The rule in words is that, if the number is even, then divide it by 2, and if the number is odd, then multiply by 3 and add 1.

In other words, define the function f from the natural numbers to the natural numbers (or f : N → N) defined by

For example, let’s take 2. It’s even, so the rule says to divide by 2, taking us to 1. Next take 7. Now that’s odd, so we multiply 7 by 3 and then add 1, landing us on 22. In this way the rule works.

Collatz’ conjecture is that if we apply f repeatedly to a natural number (positive integer), then the resulting sequence of numbers eventually arrives at one.

For example, start with 5. The result of repeatedly applying f is:

• f(5) = 3(5) + 1 = 16 (since 5 is odd);
• f(16) = 16/ 2 = 8 (since 16 is even);
• f(8) = 8/ 2 = 4 (since 8 is even);
• f(4) = 4/ 2 = 2 (since 4 is even);  
• f(2) = 2/ 2 = 1 (since 2 is even);  

If we start with 17, for example, the result of repeatedly applying f is:

• f(17) = 3(17) + 1 = 52 (since 17 is odd);
• f(52) = 52/ 2 = 26 (since 52 is even);
• f(26) = 26/ 2 = 13 (since 17 is odd);
• f(13) = 3(13) + 1 = 40 (since 13 is odd);  
• f(40) = 40/ 2 = 20 (since 20 is even);  
• f(20) = 20/ 2 = 10 (since 20 is even);
• f(10) = 10/ 2 = 5 (since 10 is even);
• f(5) = 3(5) + 1 = 16 (since 5 is odd);
• f(16) = 16/ 2 = 8 (since 16 is even);
• f(8) = 8/ 2 = 4 (since 8 is even);
• f(4) = 4/ 2 = 2 (since 4 is even);
• f(2) = 2/ 2 = 1 (since 2 is even).

A convenient way to represent the successive f values as a sequence with arrows. The successive f values for 17 are given as below:

17 → 52 → 26 → 13→ 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 …

If someone consider the number 1 and apply f on it, he/ she will get the following sequence of numbers:

Here at the end, we see we are stuck in the loop 1 → 4 → 2 → 1 → …

I couldn’t ignore it when I first learned of it. My friends and I spent days trading thrilling insights that never seemed to get us any closer to an answer. But the Collatz conjecture is infamous for a reason: even though every number that’s ever been tried ends up in that loop, we’re still not sure it’s always true. Despite all the attention, it’s still just a conjecture.

The sequences of numbers generated by repeatedly applying f to a natural number are called hailstone sequences (because the values are usually subject to multiple descents and ascents like hailstones in a cloud) with the collapse of the value when a large power of 2 appears being analogous to the impact of a hailstone. One can easily check, if we start with the number 27 then 111 steps are required to reach one and the largest intermediate number is 9232. This quite irregular behaviour of the sequence is not at all apparent in the original phrasing of the problem.

The Collatz conjecture has been checked for numbers up to 5 × 2⁶¹ (about 5.764 × 10¹⁸) by using a variety of computational tricks. It has not, however, been proven or disproven. The very simple statement of the problem causes mathematicians to underestimate the difficulty of the problem.

A simple (but incorrect) argument suggests that hailstone sequences ought to grow indefinitely. Half of all numbers are odd, half are even. The function f slightly more than triples odd numbers and divides even numbers in half. Thus, on average, f increases the value of numbers. The problem is this: half of all even numbers are multiples of four and so are divided in half twice. One-quarter of all even numbers are multiples of eight and so get divided in half three times, and so on. The net effect of factors that are powers of two is to defeat the simple argument that f grows “on average”.

Your suggestions are eagerly and respectfully welcome! See you soon with a new mathematics blog that you and I call “Math1089 – Mathematics for All!“.