Maths Ed Ideas: The Most Dangerous Problem

The 'Most Dangerous Problem' is a story about the Collatz conjecture, one of the most famous (or to some, infamous) unsolved problems in mathematics. It is a story that will help students appreciate the beautiful hidden depths of mathematics, the difference between demonstration and proof, and the excitement that surprising and difficult problems invoke in the mathematics community. Moreover, it will encourage students to frame their own learning as part of the tradition in mathematics of pure intellectual pursuit for its own sake. It can be used by teachers to support their teaching of substitution, algorithmic thinking and iteration.

Downloads:

Lesson slides (.ppt format)
Lesson slides (.pdf format)

The Most Dangerous Problem

Whereas we are unsure of the definitive, exact origin of the problem, it has become traditionally and eponymously associated with Lothar Collatz (1910-1990), a German mathematician known for his work in numerical analysis, who posed this deceptively simple looking problem in 1937. 'Such simplicity, however,' in the words of Alex Bellos, 'stands in striking contrast to the difficulty of proving the conjecture itself.'

Indeed, proving Collatz's conjecture is widely considered to be completely out of our current reach, and provoked the prolific mathematician Paul Erdős to state that 'mathematics is not yet ready for such problems.' It has been described as 'uncrackable,' called 'the simplest impossible problem,' and monikored as 'the most dangerous problem in mathematics' because ― as mathematician Jeffrey Lagarias, the World's leading expert on the Collatz Conjecture states ― 'people become obsessed with it, and it really is impossible.' Mathematician Alex Kontorovich goes further and says that if 'someone actually admits in public that they're working on it, then there's something wrong with them!' (The cartoon from the wonderful xckd.com below will give you the general gist.)

Kontorovich even describes how some people have suggested that during the cold war people thought 'it was something invented by the Soviets to slow down U.S. science... because everybody [would be] sitting there twiddling their thumbs on this trivial thing that you can tell school children.' The problem has also been called Kakutani's problem, after the mathematician Shizuo Kakutani, who relayed the 'joke' that 'this problem was part of a conspiracy to slow down mathematical research in the U.S.'

Many of those who have worked on the Collatz conjecture have warned others to 'stay away,' but despite ― or perhaps because ― of this, the conjecture continues to intrigue, beguile and seduce the World's greatest mathematicians. One of the greatest, Terrence Tao, describes the conjecture as 'one of the most “dangerous” conjectures known [because it is] notorious for absorbing massive amounts of time from both professional and amateur mathematicians.' Tao went on to question why, if the Collatz conjecture is just 'a mere mathematical curiosity, with no obvious real-world applications, ... should we try to solve it?' You can see his beautiful response on slide 21 here, and this article describes Tao's subsequent work on it, and his remarkable discovery that the Collatz conjecture is 'almost' true for 'almost' all numbers, which is the closest we've got!

The Collatz Conjecture

In short, Collatz's conjecture is that the following algorithm...

Choose any positive integer you want.
If the number you chose is even, divide it in half.
If it is odd, multiply it by 3 then add 1 (hence the \(3x + 1\)).
Repeat this process.

...will eventually produce the number 1, regardless of which positive integer is chosen initially.

Most mathematicians believe this to be true. Indeed, by 2008 we had tested Collatz's algorithm for all numbers up to \(19 \times {2^{58}} = 5,476,377,146,882,523,136\) and found that they always, eventually reached 1. By 2018, the upper limit of numbers we had tested and shown to always reach 1 was \({2^{100000}-1}\), which has over 30,000 digits and so too large to write here, and which needed to apply the \(3x + 1\) computation 481,603 times and the \( \div 2\) computation 863,323 times. As of 2024, David Bařina's computer systems checked around 220 billion numbers per second (i.e. 1.361 light mm per number) to push this upper limit to \({1.5\times 2^{70}}\), or 1,770,887,431,076,116,955,136. But none of this, of course, proves that reaching 1 is always the case. And as yet, no-one has a clue how to prove it.

Examples

If we start say with 19...

19 is odd, so we multiply it by three to get 57, then add one to get 58
58 is even, so we halve it to get 29
29 is odd, so we multiply it by three to get 87, then add one to get 88
88 is even, so we halve it to get 44
44 is even, so we halve it to get 22
22 is even, so we halve it to get 11
11 is odd, so we multiply it by three to get 33, then add one to get 34
34 is even, so we halve it to get 17
17 is odd, so we multiply it by three to get 51, then add one to get 52
52 is even, so we halve it to get 26
26 is even, so we halve it to get 13
13 is odd, so we multiply it by three to get 39, then add one to get 40
40 is even, so we halve it to get 20
20 is even, so we halve it to get 10
10 is even, so we halve it to get 5
5 is odd, so we multiply it by three to get 15, then add one to get 16
16 is even, so we halve it to get 8
8 is even, so we halve it to get 4
4 is even, so we halve it to get 2
2 is even, so we halve it to get 1

If we carried on with 1...

1 is odd, so we multiply it by three to get 3, then add one to get 4
4 is even, so we halve it to get 2
2 is even, so we halve it to get 1

We end up in the cycle 4, 2, 1, 4, 2, 1, ... So, when starting with 19, the number 1 is reached after 20 steps. Of course, some numbers take longer to 'stop' than others (see here for a list of how long each number from 1 to 10,000 takes). And this provokes other questions, that may or may not be fruitful (that's one of the joys about mathematics, we don't know sometimes where it will take us). For example, is there a longest length of numbers before getting to 1? What is the highest number generated in the sequence before reaching 1?

Consider the sequence of 111 numbers generated when starting at 27, for example, before 1 is reached. The highest number is 9232, before it falls inexorably down to 1 and then "bounces" into the small loop 4, 2, 1, .... Plotting these 'hailstone' numbers, as they've been called, because 'a hailstone eventually becomes so heavy that it falls to ground,' maps out the beautiful journey of the sequence: