Stanislav Ulam was a famous and influential mathematician of the 20th century. Among other things, he even was a member of the team of scientists who developed the atomic bomb during the days of World War II. But like many mathematicians, he had a fascination for the simplest of things: whole numbers and basic operations. He is credited for devising the little numerical activity to be described below, something so easy that it is within the scope of understanding of most any elementary school student.

	The rules of this activity are as follows:

   1.	Select any whole number.

   2.	a) If the number is even, divide it by 2.

    	b) It it is odd, multiply it by 3, then add 1.

   3.	Continue Step 2 with each result, building a sequence of numbers, until...

	well, that's what you are supposed to discover!  When
	you get to the surprise, you'll know.  (Don't read ahead
	on this page, if you want to get the maximum enjoyment
	from the activity.)

	So, try it.  Do the process many times before reading on.  I 
    guarantee that the effort will be worth it.

The Surprise

     Well, did you follow my advice? Did you try the Ulam process several times with different numbers, large and small? If so, you should have discovered that sooner or later you arrived at the number 4, which gave you 2 [Rule 2a], which in turn gave you 1 [Rule 2a], and then got a 4 again [Rule 2b]! Did that surprise you? It should have, because now you are locked into a "vicious circle", with no escape.

     And what makes this even more surprising is that, as far as we know, all numbers always arrive to the 4-2-1 loop, or cycle. No matter what you choose. Some just take longer to get there than others, that's all.

     So if all numbers do the same thing, what can we do in the math classroom to make this into a true learning activity? My advice is to ask some questions like:

     Don't let those questions scare you into thinking that there is a lot of work involved to obtain the answers. It is because as you are working with one number, you often will obtain other numbers in the 1-to-100 range as part of your sequence. Let me explain with an example.

          Choose 28 to start with. The sequence begins:

28 ==> 14 ==> 7 ==> 22 ==> 11 ==> 34 (etc.)

So while you are working on the number of steps for "28", automatically you obtain data for the other numbers. See? It's not so bad after all.

     Now, to make our work a little more organized and formal, we might apply the function concept from higher math and define a "number of steps required" function in the following manner:

     Let U(n) be the number of steps required for a number to arrive at the 4, the "entry point" for the cycle in this game (a fact that is not so in other games like this one, as you'll soon see later). This notation is read, as all algebra students soon learn, "U of n". Some examples will show how this works.

	U(20) = 5, because

		    1      2     3      4     5

		20 ==> 10 ==> 5 ==> 16 ==> 8 ==> 4 

	U(26) = 8, because

	      1      2      3      4      5     6      7     8	

	  26 ==> 13 ==> 40 ==> 20 ==> 10 ==> 5 ==> 16 ==> 8 ==> 4

     And those two examples suffice to once again emphasize that finding the number of steps for one number also produces data for other numbers at the same time, because the sequence for "20" was a part of the sequence for "26".

     Perhaps it is now time to show the U(n) values for all the numbers less than or equal to 100. Observe the chart below:

U(n) Values for the Numbers 1 - 100
nU(n) nU(n) nU(n) nU(n) nU(n)
1loop 215 41107 6117 8120
2loop 2213 426 62105 82108
35 2313 4327 63105 83108
4loop 248 4414 644 847
53 2521 4514 6525 857
66 268 4614 6625 8628
714 27109 47102 6725 8728
81 2816 489 6812 8815
917 2916 4922 6912 8928
1014 3016 5022 7012 9015
1112 31104 5122 71100 9190
127 323 529 7220 9215
137 3324 539 73113 9315
1415 3411 54110 7420 94103
1515 3511 55110 7512 95103
162 3619 5617 7620 9610
1710 3719 5730 7720 97116
1818 3819 5817 7833 9823
1918 3932 5930 7933 9923
205 406 6017 807 10023

     At this time it would be a good idea to investigate some of the interesting patterns that are present in this table.

1. U(n) = n This is true for n = 6, 15, and 18 2. U(n) = U(n+1) This is true many times. 3. U(n) = U(n+1) = U(n+2) Find the cases for this one. 4. U(n) = U(n+2) For example, n = 24. 5. U(n) = U(n+2) = U(n+4) This is true for n = 72.

     Items #2-#5 are actually the answers to Question b that was asked earlier. And Question a is answered now: 97 needs 116 steps, that is, U(97) = 116. [A nice challenge is to actually produce that monster string of numbers, a task made easier by using a calculator.]

     By way of practicing the use of inequality symbols we can now efficiently ask these questions, using the chart, of course:

How many times is U(n) < n?

How many times is U(n) > n?

Son of Ulam

     Perhaps you think we have pretty much exhausted the topic of Ulam's game by now. Well, not so. There is more, much more. For example, what if we return to the original rules and make one small change in them? Let's subtract 1 in Step 2b, instead of add 1. What effect might that have? As before, try it before you read on. (Please.)

The solutions:

     Did you notice I said solutions this time? That's because there are three types of outcomes this time. And if you did not do enough research, you might have missed one or two of them. You see, you must be careful in this sort of investigation.

     So what are those solutions?

   1.	Some numbers arrive at a very small loop: 2-1.  In fact, I

	don't like to call this result a loop at all.  Rather, a more

	descriptive name might be a "flip-flop".

   2.	A 5-term loop is produced by many other numbers; it is

	5 ==> 14 ==> 7 ==> 20 ==> 10 ==> [5].

   3.	But a much larger loop of 18 terms is also obtained; it is

	17 ==> 50 ==> 25 ==> 74 ==> 37 ==> 110 ==> 55 ==> 164 ==> 82

	   ==>41 ==> 122 ==> 61 ==> 182 ===> 91 ==> 272 ==> 136 ==> 68

	   ==> 34 ==> [17]

     It is believed by this writer that, like the first Ulam game, all numbers eventually flow into these three patterns, and only these three patterns, sooner or later in this second version. If anybody can prove this to the contrary, please let me know.

Postscript (6/11/99):

     I have found a website that gives more information about this famous problem. It can be found here.

Here is a quote from that site:

The 3x+1 problem, also known as the Collatz problem, the Syracuse problem, Kakutani's problem, Hasse's algorithm, and Ulam's problem, concerns the behavior of the iterates of the function which takes odd integers n to 3n+1 and even integers n to n/2. The 3x+1 Conjecture asserts that, starting from any positive integer n, repeated iteration of this function eventually produces the value 1.

The 3x+1 Conjecture is simple to state and apparently intractably hard to solve. It shares these properties with other iteration problems, for example that of aliquot sequences and with celebrated Diophantine equations such as Fermat's last theorem. Paul Erdos commented concerning the intractability of the 3x+1 problem: "Mathematics is not yet ready for such problems." Despite this doleful pronouncement, study of the 3x+1 problem has not been without reward. It has interesting connections with the Diophantine approximation of the binary logarithm of 3 and the distribution mod 1 of the sequence {(3/2)^k : k = 1, 2, ...}, with questions of ergodic theory on the 2-adic integers, and with computability theory - a generalization of the 3x+1 problem has been shown to be a computationally unsolvable problem. In this paper I describe the history of the 3x+1 problem and survey all the literature I am aware of about this problem and its generalizations.

Postscript: (12/8/01)

If you begin with 77,671, you reach 1,570,824,736 as the biggest number. In the end you reach 1 after 232 steps. (Source: The Kaprekar Number and more playings with numbers)

Postscript: (4/28/02)

     WTM has just encountered Tomás Oliveira e Silva's webpage, http://www.ieeta.pt/~tos . There, under the title Computational verification of the 5x+1 and 7x+1 conjectures, he writes:

Let x be an integer. Let the function T_5(x) be equal to x/2 if x is divisible by 2, equal to x/3 if x is divisible by 3 but not by 2, and equal to 5x+1 otherwise. In a similar way, let the function T_7(x) be equal to x/2 if x is divisible by 2, equal to x/3 if x is divisible by 3 but not by 2, equal to x/5 if x is divisible by 5 but not by 2 and 3, and equal to 7x+1 otherwise. Just like the 3x+1 function, it appears that, starting from any positive integer, the repeated iteration of the T_5(x) and T_7(x) functions eventually reach the integer one, after which the iterates enter a cycle. These are the 5x+1 and 7x+1 conjectures. (The 5x+1 conjecture was suggested to me by Eric Roosendaal.)

The two functions defined above are special cases of the generalized 3x+1 mapping proposed by Keith Matthews.

Next, for more than you'd probably ever need to know about this problem, click here.

Send e-mail.
Back to
Go back to
Home Page
Go back to