ULAM-421

     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

     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:

• Which number less than or equal to 100 produces the longest string of numbers necessary to arrive at the 4-2-1 cycle?



• Which numbers less than or equal to 100 require the same number of steps to arrive at the cycle?

     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:

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:

     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:

     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):

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)

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.