Category Archives: Recursive Operations

Activities about Recursive Operations

What Comes Next?

Sequential thinking is an essential element in one’s ability to experience success in various branches of math — and life, as well. Think of the sequence of steps one employs in the act of getting dressed in the morning to go to school or work: socks first, shoes second (not the other way around).

The three activity sheets in this article are intended to give the elementary student a little introductory experience in sequential thinking with letters in alphabetical order and the counting numbers. They are only meant to be samples of what the classroom teacher can prepare for his/her own students. The possibilities for the patterns are virtually endless, and even some items might have more than one possible logical response.

An R.O. for Fractions

I have always believed, contrary to general public opinion, that “FRACTIONS ARE FANTASTIC”. I have no great trouble with adding, subtracting, multiplying, or dividing these marvelous little creatures. In fact, I even take a certain amount of pleasure in doing problems with them. Of course, nowadays with the calculators that have the ability to do these computations, well, some of the fear should be removed from those of you out there who don’t feel the same as I.

Ah, I guess that’s progress; I don’t know.

But here is a little Recurrent Operation activity that involves fractions in a most unique and unusual way. Follow the steps that are stated below and you will see for yourself just how fantastic fractions can be at times.


1. Choose any two numbers to start the sequence.

2. Determine every number after the second by increasing the last existing number by one and dividing the sum by the number two places before the term being created.

Here is an example to explain the process. Let’s start with 7 and 4. The third term will be 5/7 because you add 1 to the “4” and divide the sum by the “7”. The fourth term can now be found by adding 1 to 5/7, then dividing by 4; this yields 3/7.

So far our sequence looks like this:

7,  4,  5/7,  3/7

Now, what would you do next? Of course, add 1 to the fraction 3/7, then divide by the fraction 5/7.

Then continue in like manner until you arrive at a surprising result. (Do you remmember what happened in the activities of Happy & Dizzy Numbers and Ulam?)


Of course, you’re curious if this will always happen every time, right? Well, try some more numbers. Try beginning with fractions for your first two selections; even mix in some negative numbers, if you feel adventuresome. That’s the way you really learn something in math: try it and see.

One warning here: just looking at many, many examples is not a mathematical proof that the surprising event that you have noticed by now always will occur. That, my friend, is where algebra comes to our aid! Find an algebraic proof that this activity produces a certain interesting outcome and email it to me. (See link below.)

By the way, can you find two starting numbers, whole numbers that is, that never bring about fractions as you build the sequence? It can be done.

Back-to-Front Multiplication

Introduction

While contemplating on the number curiosity below, I discovered that it possessed deeper and unexpected characteristics, structure, and patterns. I have not seen any discussion of these findings in the recreational literature I have read. Hence, it is being offered with the belief that I have uncovered a new recurrent operation pattern of a cyclic nature. It is dramatic proof that there often is a lot more structure than we realize behind most of the very innocent-appearing number puzzles.


The Problem

In the April 1962 issue of Recreational Mathematics Magazine, there appears the following multipication oddity:

421,052,631,578,947,368 can be doubled by shifting

the last digit to the front. (p. 34)

Desiring to use such fascinating problems in my school teaching at the junior high level, I wondered, “Are there more such problems, or is this just a freak case?”


The Solution

To my great surprise, once the simple secret of their construcion is understood, I found it very easy to find quite a few such examples. But, often one has to be rather patient for the required factors to reveal themselves. To facilitate the following discussion, I will demonstrate the construction method with a simple example. (This will also serve to motivate the rationale behind the recurrent operation to be described shortly.)

Say that we desire to have a problem where “4” is our single-digit multiplier, and “7” is to be the shifted unit’s digit. We begin by setting those digits in their normal places (see Figure 1a).


		          2           2  	3 2
        	7	  _ 7         8 7       _ 8 7
            ×   4       ×   4       ×   4      ×    4
		            8	        8	  4 8
              (a)        (b)         (c)	 (d)

				Figure 1

The indicated multiplication is carried out as shown in Figure 1b. Then as the “8” is the unit’s digit of the product, it follows that it must be the ten’s digit of the factor as well (see 1c). Figure 1d shows how the process is to be repeated.

But when does it stop? It’s quite simple: when you obtain a “7” to place in the product and there is no “carry” involved. In the example before us, we are fortunate to arrive at another “7” in only six steps:


			3   3   1   3   2
			1   7   9   4   8   7
			  		×   4
			7   1   7   9   4   8

In general then the process continues until such time that the shifted digit itself is the outcome of one of the steps.

By using this procedure for other original digit choices, one can produce multiplication problems that possess the back-to-front shift property for the multi-digit factor.

Table 1. Back-to-Front Multiplication Integers
Single-digit factor The Special Integers
2 105,263,157,894,736,842
3 1,034,482,758,620,689,655,172,413,793
4 102,564 128,205 153,846 179,487 230,769
5 102,040,816,326,530,612,244,897,959,183,673,469,387,755
142,857
6 1,016,949,152,542,372,881,355,932,203,389,830,508,474,-
576,271,186,440,677,966
7 1,014,492,753,623,188,405,797

1,159,420,289,855,072,463,768

1,304,347,826,086,956,521,739

8 0,253,164,556,962

0,379,746,835,443

0,886,075,949,367

1,012,658,227,848

1,139,240,506,329

9 03,370,786,516,853,932,584,269,662,921,348,314,606,741,573
10,112,359,550,561,797,752,808,988,764,044,943,820,224,719

Table 1 presents a summary of what I choose to call the “primary” solutions. These solutions were developed in the following systematic manner:

1) First I selected various digits (destined to be the shifted unit’s digits) that were equal to or greater than certain single-digit multipliers.
2) While computing all such cases, I observed that frequently a result contained the same sequence of digits; it just began at a different position.

Here is a simple example to illustrate:

		1  2  8  2  0  5	 2  0  5  1  2  8
		           ×   4	            ×   4
		5  1  2  8  2  0	 8  2  0  5  1  2

So, the “shifted-8″ case was considered redundant for my purposes, and was not included in the table. This should make it clear why there are fewer integers listed than are possible, i.e. the others are merely “embedded” in those given.

3) There were only a few cases where this embedded aspect did not account for instances in which the shifted-digit was less than the multiplier. This happened only when “8” and “9” were the multipliers, occurring three times and once, respectively. It is in such situations for all multipliers that a “leading zero” must be appended to the front of the large factor. The reason for this becomes obvious when it is pointed out that no positive integer times another can be less than the former one (whether or not there is a “carry”). In view of the way it makes things more uniform and regular, the use of the leading zero is not too great a liberty to take with standard notation., one thing is clear at this point: it preserves the equal length property of the integers, a fact that will become more apparent later.

Since further structure and pattern considerations for the integers in Table 1 will actually be covered in the discussion of the recurrent operation, we should now turn our attention to that topic.


The Recurrent Operation

While carrying out this iterative process, the tedium of writing the work in the customary manner made me aware that the digits of the product were of little use to me. So I ceased to write them at all. Then I noted that the same information could be conveyed by a vertical method. Figure 2 shows how this would be done for the “7-over-4″ example discussed earlier.


	  3  3  1  3  2        3  3  1  3  2
	  1  7  9  4  8  7     1  7  9  4  8  7         /×4/
	             ×   4                ×   4	          7
	  7  1  7  9  4  8				 28
						         34
							 19
                (a)                   (b)    	         37
							 31
							 (7)

							 (c)
				Figure 2

The recurrent operation algorithm then emerges in the 2c part, by observing these steps:

  1. Two digits are selected; one is the constant multiplier, the other is the first term of our cycle.
  2. Their product is the second term of the cycle.
  3. The next term, and all succeeding terms, is the product of the constant multiplier and the unit’s digit of the preceding term, increased by the ten’s digit (if any).

This can be summarized by the recursive formula:

Let k and a1 be the constant and first-term digits, respectively. Then,


			a2 = ka1 , and
			an = ku + t , where an-1 = 10t + u.

Table 2 was prepared by using this compact vertical format. Reading the unit’s digits from the bottom up produces the special integers given in Table 1. Table 3 (further below)is a summary of the patterns that can be found in Table 2.



Discussion of Table 3

Table 3.
Factor No. of primary cycles Cycle Period Max. Integer Omissions from
primary cycles
2 1 18 18 none
3 1 28 28 none
4 5 6 37 13, 14, 17, 23,
25, 29, 35
5 2 42 & 6 48 none
6 1 58 58 none
7 3 22 68 23 & 26
8 5 13 77 12, 14, 15, 17, 27, 33,

41, 57, 58, 61, 69, 71

9 2 44 88 none

This summary table reveals several intriguing properties for the cycles in Table 2. The first thing to note is that the multipliers 2, 3, and 6 each produce but a single primary cycle, whereas the remaining factors yield 2 or more cycles apiece. Turning to the multi-cycle cases, we see that all except the factor “5” had cycles of equal periods. The term “max. integer” simply refers to the largest integer that appeared in the normal production of the primary cycle for the factor. For the factors 2, 3, 6, and 9, it is relevant to note that the product of the cycle period and the number of cycles is equal to the “max. integer”. This shows that there are no “omissions” in the range of 1 to that largest integer. The factor of 5 also qualifies here by merely adding the two values for its cycle periods.

However, the factors 4, 7 and 8 present the most interesting facets so far. Number 7 has the fewest omissions, so let’s examine them first. Applying the R.O. algorithm. It so happens that each integer (23 and 46) yields itself immediately. In line with current terminology in such cases, I call such integers “self-generators”.

Testing the values in the omissions list for “8” shows that none of them are self-generators. However, all but one of them (i.e. 69) generate another entry in the list. Yet 69 itself generates an interesting value nonetheless: “78”, which is one greater than the max. integer. So, if we temporarily include 78, we can construct a “secondary” cycle, namely,

12 — 17 — 57 — 61 — 14 — 33 — 27 — 58 — 69 — (78) — 71 — 15 — 41; (and 41 returns to 12).

This augmented cycle now has 13 terms, just like the primary ones!

Finally, we look at the case for “4”. That set has two self-generators (13 and 26). (At this point we can note a common property shared by our two pairs of self-generators: namely, the smaller one is half the larger.) As we did for the 8-case above, another secondary cycle can be formed by using the remaining values. This time we must also temporarily include the integer that is one greater than the max. integer. This last cycle is

14 — 17 — 29 — (38) — 35 — 23 — 14.

And the equal-period property is preserved!

Now, upon glancing back to Table 3, we can appreciate the full significance of the max. integer column by noting that only the “4” and “8” cases had a largest entry ending in a “7”; and only those two yielded secondary cycles that necessitated the restoration of the “missing link”, so to speak. With the inclusion of those two missing links, everything “ends with an 8″.

That strange finding naturally raises the question: “What about all those values that immediately follow those 8-enders, namely, 19, 29, 39, … , 89?” Well, oddly enough they all turn out to be self-generators for their respective single-digit factors! And this fact extends beyond the table, and is easily proved as follows:

[10(n – 1) + 9]n = 9n + (n – 1) = 10n – 1.

(The final expression is the same as what is inside the brackets.)


Conclusion

This brings me to the end of my discussion into this puzzle, except for two closing comments and a challenge. The systematic manner in which the data was gathered proves that the contributor of the original puzzle could not have presented a shorter integer than one with 18 digits. The cycle periods given herein are all minimums.

Also, it is very easy to see that all the integers (no matter how large), under this R.O. procedure reduce to only the cycles or self-generators given in this paper. This is a factor that parallels the well-known R.O. procedure concerning the sums of the squares of the digits of all integers (see the Steinhaus or Trigg references). [Also click on Happy & Dizzy Numbers for more information in this website.]

Finally, a challenge to the reader. What patterns, and periods, and other phenomena occur when integers in other bases are put through this new recurrent operation? Try them, and see for yourself!


References

  1. Steinhaus, Hugo. One Hundred Problems in Elementary Mathematics. New York: Basic Books, 1964, pp. 11-12, 55-58.
  2. Trigg, Charles W. “A Close Look at 37,” Journal of Recreational Mathematics, 2(2), April 1969, pp.117-128.

[Published in The Oregon Mathematics Teacher, Feb. 1978, pp. 22-27.]

Palindrome Power

PALINDROMES: A Teacher’s Guide

A number that remains unchanged in value upon writing it in reverse is called a palidromic number, or simply a palindrome. The idea is borrowed directly from a popular form of word play. Certain words, like dad, noon, radar, etc. possess this reversal invariant property. Even many sentences can be formed that also exhibit it. Examples: Madam, I’m Adam. and Rats live on no evil star. Of course, here we will mainly be concerned with the numerical version, though the use of palindromic words should not be ignored as a means of explaining this concept to students.

[Note: The word palindrome is derived from the Greek palíndromos, meaning running back again (palín = AGAIN + drom-, drameîn = RUN). A palindrome is a word or phrase which reads the same in both directions. (Source: What are palindromes?)]

The teacher has two possible methods of introducing palindromes to the student: the direct and the indirect. The former consists of a straightforward definition (“A palidrome is ….”), followed by examples and appropriate exercises.

However, this writer believes that the indirect approach provides an excellent opportunity to provide students with a moderately easy situation to test their observation skills. Our success with students at a wide variety of levels has led us to this conclusion. However, you, as the teacher, may devise your own method of presentation. Here is our basic method.

We begin by presenting a few examples of numbers that are palindromes, and asking if anyone sees what makes these numbers special. We start with three-place numbers and gradually present larger ones. Depending on the responses received, we at times present numbers that are NOT palindromes, for contrast. Other times, we give a number that meets the criteria of the students’ attempts of definition, yet is not a palindrome. By being patient, the proper definition usually is deduced with little help from us. Then we proceed to the reverse-and-add activity to be described below.

Once the definition has been “discovered”, we then introduce “things to do” with it. The one that provides the most interest is the Reverse-and-Add procedure. It is quite simple:

  1. Pick a number, any number.
  2. Reverse that number, writing it beneath the other.
  3. Add the two numbers.
  4. If a palindrome results, “Voila! Eureka!”; if not, reverse that sum underneath itself, and continue until such time as one is obtained.

Simple as it is — and it REALLY is — it is impossible in a practical sense to just say when, if ever, a palindrome will be encountered. Sometimes it occurs at the first or second addition, other times it requires lots more. For example, 89 does not yield one until the 24th addition, consisting of 13 digits. [To see an actual account of what happened one day in my class, click here.]

Another enigma is the number 196. Here it is literally not known whether a palindrome will appear. A computer has performed over 4000 additions on it [see update below], and none has shown up yet. However, this, like Goldbach’s Conjecture, does not prove the case. It just says the problem is beyond the paper-and-pencil method of solution.

But to return to our classroom work, we present a variety of examples in the following manner (with variations, of course):

                      38      85        475
                    + 83    + 58      + 574
                     121     143       1049
                           + 341     + 9401
                             484      10450
                                    + 05401
                                      15851

From this point on, various lines are possible. One is to give the three numbers 195, 196, and 197 and ask the students to find palindromes. Usually 195 is done first, with a palindrome appearing at the 4th addition step. This is followed by 197; its palindrome appears on the 7th step. But as stated above, 196 is a mystery. So to spark interest and enthusiasm, we offer a “reward” to the first person who finds a palindrome correctly computed from 196. This never fails to get them working frantically. Of course, while this may seem to be an unfair problem, there are many lessons than can be learned in this sort of exercise. Invariably, students start announcing that “I’ve found one!” You know in advance that an error of some kind has been committed. With care, you will locate a basic fact error, or one involving improper carrying, or improper reversing, etc., etc. A bit of advice is in order here: prepare yourself with a list of the first 25 or so sums to make it more efficient in locating the point at which an error was made (it may not be the only one, or even the first). Also, take extreme care in making your list, lest you commit an error yourself. (It CAN and does happen, even to the best of us.)

Another approach we have taken, with equally interesting results, is to offer 25 cents to the first person who finds a palindrome based on 89, correctly computed. [Note: this article and work was originally done in the late ’70s, when a quarter was a bit more attractive. But, even then, 25 was an essential part of the activity.] This of course, is possible; and the payoff is “fair” — virtually 1 cent per addition. Yet, to discourage sloppy or careless work, we offer a counter-bet of 5 cents that the student must pay us IF an error can be found. Of course, we don’t take the students, as somebody either wins from the class, or the money is returned to them. This makes some students be a little more careful and aware that even in an apparently simple problem, one can make mistakes. As time passes and a few (2 or 3) losers have had to pay up, we give the hint that they had better do more than 20 addition steps, or refuse to look at their work (knowing they haven’t spent enough time on it and should look for their own mistakes). After this problem is conquered, we present the 196 case, with an appriately greater reward (e.g. $10). Other times we give them the choice of problems.


There are other types of palindrome processes. The reverse-and-add procedure can be modified to ask the question: If you keep on going with the R&A work, how many palindromes appear in 10 (or 15) addition steps? Other questions include: Does a palindrome yield a palindrome? How many palindromes can come up “in a row”? Can a palindrome only occur if there has not occurred a “carry”? (Can you think of your own?)

Palindromes can arise in other settings. For example, squaring, cubing, or finding other powers of certain numbers will yield palindromes. How many can you find?


Encouraging students to be on the lookout for strange or unique numbers ca have interesting ramifications. Ask them to be alert and see who can find a license plate number that is a palindrome. Or a phone number, a social security number, a house address, a zipcode. Since numbers are all around us in this modern world, we ought to make them our friends. In other words, “Let’s don’t fight it. Learn to recognize interesting numbers with strange properties. Then it is more like hunting for diamonds or nuggets of gold. We appreciate them more for their rarity or unique characteristics.”


[NOTE: (July 2001) I have recently been introduced to Patrick De Geest of Belgium. He has a marvelous website devoted largely to alindromes, called WORLD!Of Numbers. Go there soon.]

[UPDATE: (February 2002) The number of reversal steps has been increased to many millions. Click here to learn more.


Below is a sample of a worksheet that could be developed to give elementary students some nontrivial investigation experience. Whether calculators should be allowed on this work is an open question. But sometimes, as in the “196” and “89” problems, the display window of the calculator is too small to contain the sums; so there it is “back to basics”, I guess: good ol’ paper-and-pencil.


1. JUST FOR PRACTICE: make sure that you understand the “reverse- and-add” procedure by completing this table.

Seed No. No. of additions Palindrome
283 3 .
185 . 4774
3947 2 .
275 . 44444

2. in each pair below produce the same palindrome, but they don’t need the same number of additions. So, for each pair, (a) find the palindrome for each pair; and (b) state the number of additions for each number.

(a) 6228 & 2673 (b) 197 & 5873

3. The seed numbers in this group all produce palindromes that have a strange common property. Find the palindrome for each, then state what the strange thing is. (Can you find a seed number of your own that will do the same thing?)

(a) 338 (b) 676 (c) 726 (d) 7482 (e) 53877

4. Here the “problem numbers” tell you how many additions are required to find a palindrome.

(1) 47 (2) 238 (3) 86 (4) 78

(5) 6358 (6) 62354 (7) 118471 (8) 8779

Can you find a seed number that requires 9, 10 or more additions? There are many.

5. The seed numbers 428, 527, and 626 all yield the same palindrome with the SAME number of additions. Look at them closely to see the pattern; what is it? Then give another number (less than 428) that belongs to this family BEFORE trying it. Finally, prove your choice is correct. (Using that idea, can you give several seed numbers that produce 15851? HINT: See exercise #1 above.)

*6. Prepare a short report by investigating the patterns you find when you use the ten numbers in this sequence:

606, 616, 626, 636, … , 696.

tt(1/29/77)

Happy & Dizzy Numbers

INTRODUCTION

Before we can explain what a happy number is, you have to learn a new idea, called “recurrent operations.” As the word “recur” means “to happen again”, a recurrent operation must mean a mathematical
procedure that is repeated. A very simple example would be the rule “add 5 to the result”. If we started with the number 0 and applied that recurrent operation rule, we would produce the sequence 0, 5, 10, 15, 20, … ; this list is the famous “multiples of five”.

Of course, there are all kinds of recurrent operation rules in mathematics. Another important rule is “multiply each result by 2″. If we used 1 as our first number, this sequence shows up: 1, 2, 4, 8, 16, 32, … ; this list is the also famous “powers of two”. So, you see it’s really not such a difficult idea now, is it?

However, in order to produce “happy numbers”, we will invent a rule that is just a little bit more complicated. (After all, you
didn’t expect this to be that easy, did you?) Our rule now will be given in two steps: (1) find the squares of the digits of the starting number; then (2) add those squares to get the result that will be used in the repeat part of your work.

Here is an example. Let’s start with 375. We write:

32 + 72 + 52 = 9 + 49 + 25 = 83

Now we repeat the R.O. procedure with 83. This gives us:

82 + 32 = 64 + 9 = 73

Of course, we continue with 73. This will produce 58.


HAPPY NUMBERS

But we can hear you saying: “When do I stop? What’s the point of all this?” That’s the beautiful part of the story. The answer is: when you see something strange happening. The strange thing that tells when a number is happy is simply this: the result of a 1 eventually occurs. Here is an example, starting with the number 23:

4 + 9 = 13; 1 + 9 = 10; and 1 + 0 = 1.

It’s that easy! When you reach a 1, the starting number is called happy. [But don’t ask why it’s happy, instead of sad; that’s just what the books say.]

Once you determine a number is happy, you can say all the intermediate results are also happy. The numbers 13 and 10 must also
be considered as happy, because they too produce a 1.

Can you find some more happy numbers? Yes. If you know a certain number is happy, it’s easy to find many more. How? One way
is to insert a zero or two. Look: above we saw that 23 was happy, right? This means that 203 is also happy; so is 230. A larger example is 2003. See? Now you can make many, many happy numbers, using an old one with as many zeros as you wish.

But that’s the easy way. You want something a bit more challenging, don’t you? Well, that’s your task now — find some more happy numbers without using the “zeros” technique. Okay?


Part II: Dizzy Numbers

The term “dizzy numbers” was invented by me. It is based on an idea that should occur to anyone searching for happy numbers, because often they find themselves “going in circles”, literally, i.e. getting
dizzy. Here’s why:

Recall the number 375 from above? It produced the sequence 83, 73, 58,… But we stopped there in our explanation of the RO procedure. If we had continued, we would have had 89, 145, 42, 20, 4, 16, 37, and then back to 58! Hmm… now that’s strange, isn’t it? We’ve returned to where we were (58) just eight steps earlier; we’ve gone in a circle. We’ve produced an 8-term numerical cycle. Hence, we’re getting a little dizzy. (Get it?)

So we can now define more formally a dizzy number to be one that is either part of that cycle or produces a sequence that enters the cycle eventually (like 375 did).

Now, do you want to hear something really strange? All numbers that are not happy are dizzy! That’s right. No matter how big or small a number may be, if you use the sum-of-the-squares-of-the-digits RO procedure on it, you either reach a 1 or the 8-term cycle. Amazing,
isn’t it?

Now armed with this new knowledge, you are ready to classify any number as happy or dizzy.

Have fun!


For more activities about recurrent operations, go to Kaprekar or Ulam.


Update: (6/24/02)

For additional information about this interesting topic, go to Mathews: Happy Numbers.

Beyond Ulam

On the 14th annual American Junior High School Mathematics Examination (1998) there appeared the following problem, which I share with you here:


Problem #22:

Terri produces a sequence of positive integers by following three rules. She starts with a positive integer, then applies the appropriate rule to the result, and continues in this fashion.

Rule 1: If the integer is less than 10, multiply it by 9.

Rule 2: If the integer is even and greater than 9, divide it by 2.

Rule 3: If the integer is odd and greater than 9, subtract 5 from it.

A sample sequence: 23, 18, 9, 81, 76, …

Find the 98th term of the sequence that begins with 98, 49, …

(A) 6     (B)  11     (C)  22     (D)  27     (E)  54

Perhaps at first glance this appears to be sort of a hard problem, or at the very least a time consuming one. Especially when you realize that it is the 22nd item on a 25-item contest exam for which there is a 40-minute time limit.

But on closer examination it soon becomes apparent that there is a cyclic pattern involved in the terms that result from applying the three rules. The sequence begins this way:

98, 49, 44, 22, 11, 6, 54, 27, 22, …

Do you see that very quickly one of the numbers repeats itself? The number 22 arose in the 4th and 9th positions. This means there is a repeating cycle of five terms.

Our goal is to determine the 98th term. But if we remove the first three, the problem reverts to one which asks:

What is the 95th term of a string of terms that occur in groups of five?

Of course, it would be the 5th term of the cycle! Hence, the correct response to the question above is 27. What once seemed a lengthy sort of solution turned out to be incredibly short.


This looks a lot like something that was discussed in this website in an earlier article, the Ulam problem. In that article we had cycles of numbers occurring also. And this resembles a famous class of problems that make the rounds of many math contests, ones like

What is the 1000th digit in the decimal form of 1/7?

What is the unit’s digit of 31998?

and so on. [See The 100th Letter.]


But there’s more, much more to this problem than just getting the answer of 27. Recall that in the Ulam article we analyzed what happened when the rules given there were applied to many different numbers — specifically all those from 1 to 100. By way of refreshing your memory, we will state the general results here. For the first set of rules, all numbers sooner or later arrived to a simple three-term cycle of 4, 2, 1 (which returned to 4). For the second set of rules, all numbers entered one of three distinct cycles of varying numbers of terms (lengths of 2, 5, and 18).

Well, what about this new set of rules? Do all numbers flow into the cycle shown above? Or are there other cycles? One more? Two? How many? You see, after solving the original contest item, the real fun begins; now it’s time to do the real mathematics! I leave this matter in your hands now. I don’t want to spoil your pleasure at discovering the results for yourself.


Extensions

Surprise! Surprise! It’s not over yet. (You thought you were through with your homework, didn’t you?)

You see, problems like this one for me are like eating popcorn, once I start asking questions, I just can’t stop. The original contest problem from the AJHSME seems to me to be just one of many possible scenarios. The three rules as given are just begging to be adapted slightly to produce new problems. Here is an example of what we mean:

What cycle or cycles result from these rules?

  1. If the integer is less than 10, multiply it by 9.
  2. If the integer is even and greater than 9, divide it by 2.
  3. If the integer is odd and greater than 9, subtract 3 from it.

Did you notice the small change in the third rule? Now we subtract 3 instead of 5 from all odd numbers greater than 9. Small change, you say? True enough. But that little change is probably going to change our cycles quite a bit, don’t you think? Investigate this one to see what happens.

Then after that, try this:

What cycle or cycles result from these rules?

  1. If the integer is less than 10, multiply it by 7.
  2. If the integer is even and greater than 9, divide it by 2.
  3. If the integer is odd and greater than 9, subtract 5 from it.

This time we retained the subtraction of 5 in Rule #3, but changed Rule #1 to “multiply by 7″. Again, this subtle change makes a big difference in the outcomes, as I’m sure you’re beginning to suspect. But just what are the resulting cycles? That’s what I leave to you to find out. In general, we have before us a whole family of problems, similar in basic structure, but each one with its own distinct character. Very probably you can now begin to create your own variations of the original problem. You could change the subtraction value in Rule #3 to other odd numbers, like 1 or 7, or 9. [What would happen if an even number were used?] And you could change the multiplier in Rule #1 to some other value as well. But Rule #2 is probably better left as is, because not all even numbers are divisible by other numbers. To do so would bring up the nasty trouble of what to do with the “remainders”!


POSTSCRIPT

Send me the results of your research. I’d like to hear about what you have found.

For more activities of a simple cyclic nature, look at Happy & Dizzy Numbers, or Kaprekar.

For more information about the AJHSME [renamed as AMC 8], contact

Titu Andreescu, Director

American Mathematics Competitions

University of Nebraska-Lincoln

Lincoln, NE 68588-0658 U.S.A.

Tel: 402-472-6566, Fax: 402-472-6087

eMail: amcinfo@unl.edu

Ulam

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

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
n U(n) n U(n) n U(n) n U(n) n U(n)
1 loop 21 5 41 107 61 17 81 20
2 loop 22 13 42 6 62 105 82 108
3 5 23 13 43 27 63 105 83 108
4 loop 24 8 44 14 64 4 84 7
5 3 25 21 45 14 65 25 85 7
6 6 26 8 46 14 66 25 86 28
7 14 27 109 47 102 67 25 87 28
8 1 28 16 48 9 68 12 88 15
9 17 29 16 49 22 69 12 89 28
10 14 30 16 50 22 70 12 90 15
11 12 31 104 51 22 71 100 91 90
12 7 32 3 52 9 72 20 92 15
13 7 33 24 53 9 73 113 93 15
14 15 34 11 54 110 74 20 94 103
15 15 35 11 55 110 75 12 95 103
16 2 36 19 56 17 76 20 96 10
17 10 37 19 57 30 77 20 97 116
18 18 38 19 58 17 78 33 98 23
19 18 39 32 59 30 79 33 99 23
20 5 40 6 60 17 80 7 100 23

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.

Kaprekar-6174

No, that is not someone’s telephone number up there in the title of this piece. It is the name of a numerical puzzle guaranteed to spark wonder and amazement in the minds of your students. It is called Kaprekar’s (pronounced kuh-PREE-kur) Constant*. This little, mysterious math activity is one of a family of math procedures called Recurrent Operations.

Recurrent operations are repetitive procedures wherein each intermediate result (i.e. sum, difference, etc.) is used in turn until a specific outcome is ultimately obtained. The procedure to work the Kaprekar sort of “magic” is as follows:

   1.	Select a four-digit number, for example, 5634.

   2.	Form a new number from this number by rearranging the
	digits in decreasing order, e.g. 6543.

   3.	Reverse the number obtained in Step 2, then subtract the
	smaller number from the larger one.

			  	  6543
				- 3456
			  	  3087 

   4.	Take the difference just obtained and repeat the procedure
	in Step 2 and 3; that is, order the digits, reverse, and
	subtract.  This should be continued until the surprise hits
	you.

		  8730		  8532		  7641
		- 0378		- 2358		- 1467
		  8352		  6174		  6174

Do you notice that with 6174 the process comes to a “stand-still”? That is, 6174 just yields itself!

But the real surprise is yet to come.


Try the procedure on any other four-digit number. It always ends with 6174. This is a famous number in the field of recreational mathematics; it’s called Kaprekar’s Constant.


Students find this discovery quite fascinating and unexpected, so much so that they don’t even realize that one of your instructional objectives is to provide some practice in subtraction skills. But more importantly you can now use this opportunity as a springboard for further exploration by posing the following questions to them:

   1.	Who can find a number that requires the greatest number
	of subtractions to obtain 6174?

   2.	What happens if the Kaprekar process is applied to three-
	digit or five-digit numbers?  (Dare we ask about still
	larger numbers?)

   3.	What happens if numbers in bases other than ten are used?
	For example, 4-digit numbers in "base 5".

   4.	Why does the game not work on such numbers as 3,333 or 888?

Many things could be said in favor of such activities from a pedagogical viewpoint, but only one will be mentioned here. Due to the strangeness of the whole situation and the interest created thereby, it causes the student to generate his own “problem set” of several exercises, based from only one or two starting numbers. That is to say, by asking him to do “only one or two problems”, he eventually does quite a few individual exercises — and enjoys it all the while.

One final note: if experience in systematic discovery is of more value to your instructional goals than merely subtraction practice, Questions #1 and #2 above make excellent investigations for pocket calculators.


*Discovered by Shri Dattathreya Ramachandra Kaprekar (1905-86?), a mathematician from India. He devised this activity in 1946 or 1949. See his photo on the right.

Additional websites that contain information about this topic:

  1. The Kaprekar Number and more playings with numbers
  2. Mudd Math Fun Facts: Kaprekar’s Constant
  3. Mathematical Black Holes
  4. Scientists of India – D.R. Kaprekar
  5. Sort, Reverse, Subtract
  6. Kaprekar Numbers
  7. More on Kaprekar’s Contants
  8. Mathews: Kaprekar Process (Highly recommended!)

Taken from T. Trotter, “Kaprekar”. Math Lab Matrix, Fall 1976, p. 8.


Number Sequences

[Preface NOTE: The material presented below was lifted from an article I saw some time ago by Dan Brutlag, “Making Your Own Rules”. THE MATHEMATICS TEACHER, November 1990. pp. 608-611. What is being given below is how I prepared a handout to give to my classes, mostly as anactivity for use by a substitute.]


NUMBER SEQUENCES

Students: I found the information below in a math magazine. I think you will find it interesting, as I did.

YOUR ASSIGNMENT:

  1. Study/investigate the results of applying the rules below to many different numbers. Keep good records to see if something “special” always happens. Describe what you find.
  2. Then make up a set of rules of your own to investigate, similar to or completely different from the samples given. Use the table of ideas that you find at the end of this handout to help you with this. Write up a little report about what you discover.

A. Lori’s Rule

  1. Start with any three-digit number.
  2. To get the hundreds digit of the next number in the sequence, take the starting number’s hundreds digit and double it. If the double is more than 9, then add the double’s digits together to get a one-digit number.
  3. Do the same thing to the tens and units digits of the starting number to obtain the tens and units digits of the new number.
  4. Repeat Steps 2 and 3 as often as necessary to find the special happening.

Example: 567, 135, 261, 432, ???, ???, …

B. Barbette’s Rule

  1. Start with any three-digit number.
  2. Add all the digits together and multiply by 2 to get the hundreds
    and tens digits of the next number in the sequence.
  3. To get the units digit of the next number, take the starting
    number’s tens and units digits and add them. If the sum is more than 9, add the digits of that sum to get a one-digit number for the units place.
  4. Repeat Steps 2 and 3 as often as necessary to find the special happening.

Example: 563, 289, 388, 387, ???, ???, …

C. Ramona’s Rule

  1. Start with any three-digit number.
  2. Obtain the next number in the sequence by moving the hundreds digit of the starting number ito the tens place of the next number, the tens digit of the original number into the units place of the next number, and the units digit into the hundreds place.
  3. Then add 2 to the units digit of the new number; however, if the sum is greater than 9, use only the units digit of the sum
  4. Repeat Steps 2 and 3 as often as necessary to find the special happening.

Example: 324, 434, 445, 546, ???, ???, …

D. Lisa’s Rule

  1. Start with any three-digit number.
  2. If the number is a multiple of 3, the divide it by 3 to get a new number.
  3. If it is not a multiple of 3 then get a new number by squaring the sum of the digits of the number.
  4. Repeat Steps 2 and 3 as often as necessary to find the special happening.Example: 315, 105, 35, 64, ???, ???, …

    Example: 723, 241, 49, 169, 256, ???, ???, …,


    TABLE OF ATTRIBUTE LISTS

    NUMBER OPERATORS NUMBER PROPERTIES
    Add ___ to ___ Divisible by ___
    Move to another position Hundreds, tens, or units place
    Take positive difference Prime
    Double Composite
    Square Even, Odd
    Halve (if even) Multiple of ___
    Multiply by ___ Greater than
    Replace by ___ Less than
    Exchange Equal to

    Postscript (7/29/99)

    Here is a personal sidelight to this activity. On April 23, 1991, I designed my own sequence rule-set. Here it is.

    TROTTER’S RULE

    1. Start with a four-digit number.
    2. To get the thousand’s digit and hundred’s digit of the next number, double the sum of the first three digits of the original number, that is, the thousand’s, hundred’s, and ten’s digits. (If this result is only a one-digit number, append a 0 to the left of that number, so a “6” would become “06”.)
    3. To get the ten’s and unit’s digit of the next number, double the sum of the last three digits of the original number, that is, the hundred’s, ten’s, and unit’s digits. (If this result is only a one-digit number, do as was done in Step #2.)