One day in the mid-1980s, Jeff Lagarias, a mathematician employed by AT&T, gave a lecture about a problem on which he had spent a considerable amount of time but for which he had found no solution. In fact, he had not even come close. It was a dangerous problem he continued, obviously speaking from experience, because those who work on it were in danger of compromising their mental and physical health.

What is this dangerous problem?

In 1932 Lothar Collatz, a 20-year-old German student of mathematics, came across a conundrum that, at first glance, seemed to be nothing more than a simple calculation. Take a positive integer x. If it is even, halve it (x/2); if it is odd, multiply it by 3, add 1, and then halve it: (3x + 1)/2. Then, using the result, start over again. Stop if you hit the number 1; otherwise continue.

Collatz observed that starting from any positive integer, repeated iterations of this procedure sooner or later lead to the number 1. Take, as an example, the number 13. The resulting sequence consists of the numbers 20, 10, 5, 8, 4, 2, and 1. Take 25. You get 38, 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, and 1 again. No matter which starting number Collatz tested, he always ended up with the number 1.

The young student was taken aback. The number sequence could have just as easily veered off toward infinity or entered an endless cycle (not containing 1). At least that should have happened occasionally. But no, the sequences ended up at 1 every single time. Collatz suspected that he might have discovered a new law in number theory. Without further ado he set about seeking a proof for his conjecture. But his efforts amounted to nought. He managed neither to prove his conjecture nor to find a

counterexample, that is, a number sequence that does not end with 1. (In mathematics it suffices to find one counterexample to disprove a conjecture.) Throughout his life Collatz was unable to publish anything noteworthy about this conjecture.

Some time during the Second World War, the problem was picked up by Stanislaw Ulam, a Polish mathematician who held a high position with the Manhattan Project. To while away his free time (there was not a whole lot to do in Los Alamos in the evenings), Ulam investigated the conjecture but failed to find a proof. What he did do was describe it to his friends, who from then on called it Ulam’s problem.

Another few years went by and Helmut Hasse, a number theorist from the University of Hamburg, stumbled over this curious puzzle. Caught by the bug, he gave lectures about it in Germany and abroad. One attentive member of the audience observed that the number sequence goes up and down like a hailstone in a cloud before it invariably plummets to earth. Time for a name change then—the number sequence was henceforth called the Hailstone sequence and the prescription to calculate it the Hasse algorithm. When Hasse mentioned the problem during one of his lectures at Syracuse University, the audience at that particular event named it the Syracuse problem.

Then the Japanese mathematician Shizuo Kakutani lectured on the topic at Yale University and the University of Chicago, and the problem immediately became known as the Kakutani problem. Kakutani’s lectures set off efforts by professors, assistants, and students as feverish as they were futile. Proof eluded everyone. Thereupon a rumor started to make the rounds that the problem was, in fact, an intricate Japanese plot intended to put a brake on the progress of American mathematics.

In 1980 Collatz, whose initial contribution had been all but forgotten, reminded the public that it was he who had discovered the sequence. In a letter to a colleague he wrote: ”Thank you very much for your letter and your interest in the function which I inspected some fifty years ago.” He went on to explain that at the time there had

only been a table calculator at his disposal, and he had therefore been unable to calculate the Hailstone sequence for larger numbers. As a postscript he added: “If it is not too immodest, I would like to mention that at the time Professor H. Hasse called the conundrum the ‘Collatz problem’.”

In 1985 Sir Bryan Thwaites from Milnthorpe in England published an article that left little doubt as to who he thought the author of the conjecture was. The article was entitled “My Conjecture.” Thwaites went on to claim that he had been the originator of the problem three decades earlier. In a separate announcement in the London Times, he proposed a prize of £1,000 to whomever would be able to provide a rigorous proof for what henceforth should be called the Thwaites conjecture.

In 1990 Lothar Collatz, who had made a name for himself as a pioneer in the field of numerical mathematics, died shortly after his 80th birthday. He was never to find out whether the conjecture that—he would have been happy to know—is nowadays usually called the Collatz conjecture was true or false.

In the meantime mathematics had found a new tool—the computer. Today just about anybody can prove on his or her PC that Collatz’s conjecture is correct for the first few thousand numbers. In fact, with the help of supercomputers, all numbers up to 27 quadrillion (that is, 27 followed by 15 zeros) have been tested. Not one was found whose Hailstone sequence did not end with 1.

Such numerical calculations do not represent a proof, of course. All they achieved was the discovery of several historical records, one of which was the discovery of the longest Hailstone sequence to date: a certain 15-digit number whose Hailstone sequence consists of no less than 1,820 numbers before it reaches the final position of 1. One thing Jeff Lagarias did manage to prove in the course of his frustrating endeavors was that a counterexample—should one exist—would have to have a cycle comprising at least 275,000 way points.

So a computer is of little help in finding a counterexample to the Collatz conjecture. In the final analysis, the ques-

tion is not decidable by computer anyway because only numbers that fulfill Collatz’s conjecture, that is, whose Hailstone sequences go to 1, will induce the computer program to stop. If indeed there exists a counterexample—either because its Hailstone sequence tends toward infinity or because it enters a very long cycle that does not contain 1—the computer program would simply produce numbers, without terminating. A mathematician sitting in front of the computer monitor would never have a way of knowing whether the sequence eventually escapes toward infinity or starts on a cycle. At some point he would probably simply hit the Escape key and go home.