Syracuse Problem

I built a Lab for you to play with the Syracuse Problem and to learn to use spreadsheets to play with like problems in fun and interesting ways. The Syracuse Problem is a simple one. Pick a number, any whole number. If it is even divide it by 2, if it is odd multiply it by 3 and add 1. If you keep doing this to each number in turn you will get the same sequence no matter what number you first pick. It is wild and totally not intuitive. You will also learn to use formulas to test whether numbers are even or odd, and even more importantly to use if…then rules. And you will learn about convergent number patterns.

I read about this problem in a most wonderful book, The Birth of a Theorem by Cedric Villani. I don’t think I have ever read a book that I understood less of and yet enjoyed as much. Villani is a Fields Medalist. For those of you who may not know, the Fields Medal is in essence the Nobel Prize of mathematics. In the book Villani tells the story of the development of the theorem that won him the Medal. I find his description of mathematics invention fascinating, for despite its esoteric nature it is the same as invention in all disciplines. As part of his story he tells about one of John Nash’s great discoveries, yes the John Nash of an Elegant Mind. And he describes a fascinating mathematical pattern that has thus far eluded explanation.

I quote from the book because Villani not only describes the problem beautifully, but he helps us all see what mathematics and mathematics invention is like.

The Syracuse problem (also known as the Collatz conjecture or the 3n+1 problem) is one of the most famous unsolved enigmas of all time. Paul Erdos himself is on record as saying that mathematics is not yet ready to confront such monsters.

Enter the expression “3n+1” in an Internet search engine and follow the thread back to the abominable problem and its result, as simple and insistent as the refrain of a pop song:

Take any whole number you like, say 38.

The number is even. Divide it by 2 and you get 19.

The last number is odd. Multiplying by 3 and adding 1 you get 19*3+1=58.

This last number is even. Divide it by 2….

And so on. You go on from one number to the next by means of a simple rule: each time you encounter an even number, divide by 2; each time you encounter an odd number, multiply by 3 and add 1.

Starting from 38, as in the example above, you get the following sequence: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1…

Once you arrive at 1, in other words, you know what comes next: 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1…ad calculam aeternam.

Every single time this calculation has been performed in the course of human history, it has ended up as 4, 2, 1… Does that mean it will always turn out thus, no matter which number is chosen as the point of departure?

Since there are infinitely many integers, obviously it’s impossible to try all of them. With all the pocket calculators, desktop calculators, computers, and supercomputers at our disposal today, it has been possible to try billions and billions of them, and every single last one has wound up leading back to the implacably repeating 4, 2, 1 pattern.

Mathematics is democratic, of course, and anyone is free to try to show that this sequence embodies a general rule. Everyone believes the rule to be true, but since no one knows how to prove it, it remains a conjecture. Whoever succeeds in confirming or disconfirming this conjecture will be proclaimed a hero.

I am certainly not among those who will try. Apart from the fact that it seems to be phenomenally difficult, it isn’t the sort of problem that suits the way my mind works. My brain isn’t used to thinking about such things.

Cedric Villani, Birth of a Theorem, p.173