15/08/2018

Mathematical problems: what seems easy can be very difficult.

Here's a spectacular example of how a mathematical problem can be incredibly easy to formulate and incredibly difficult to solve.

It works like this: consider any positive integer N. If it's even, divide it by 2. If it's odd, multiply it by 3 and add 1. Replace N with the result obtained and continue repeating this procedure. For example, if you start with N=7 you will successively obtain 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 and, from then on, the sequence only repeats the numbers 4, 2, 1, cyclically.

If you start with a different value of N, the sequence will be different, of course, but sooner or later it will reach the number 1. The number of operations until this happens, called the stopping time, depends in a complicated way on the initial number N. But sooner or later it always happens.

At least that's been the case for all numbers tested to date. With the advent of computers, it became possible to test increasingly larger numbers; nowadays we know that the property of arriving at the number 1 holds true, at least, for all numbers N with fewer than 21 digits.

But no one has yet been able to provide a rigorous mathematical proof that it holds true for all integers, despite all the efforts made since the problem was raised in 1928 by the German mathematician Lothar Collatz (1910–1990). In fact, there has been very little progress.

The famous Hungarian mathematician Paul Erdös (1993–1996) once said that “perhaps mathematics is not ready for problems like this,” meaning that there are no tools to tackle it. He also offered $500 for the solution, and that prize still stands.

An interesting breakthrough, which also illustrates the subtlety of the problem, was achieved by John Conway and improved by Stuart Kurtz and Janos Simon. In a slightly more general context, they proved that the problem is computationally undecidable: there is no computer program capable of telling for every N whether the sequence will reach 1 or not.

To read the full text, visit the newspaper's website or check the print version.

Folha allows each reader access to ten articles per month even without a subscription.