Lately, I've been reading Kurt Gödel's biography by John Dawson. The book is lucid and informative. Like every absorbing reading, it overflows one's expectations. Gödel earned his Ph.D. in early 1930. Three important results were established in his dissertation: the completeness of the first-order calculus, the independence of the axioms he employed, and a compactness theorem that derived satisfiability of a countable set of first-order formulas from that of its every finite subset. None of this was enough to qualify him for gainful employment in the academic field. For this, among other requirements, he had to write another major paper.

Being extremely confident in his mathematical ability, Gödel chose to tackle the second Hilbert problem of proving the consistency of the axioms of arithmetic — a positive claim. By his own account, he set out to advance Hilbert's program. But the result he found towards the fall of 1930 that is now known as Gödel's first incompleteness theorem, was profoundly negative: there exist arithmetic statements that are formally undecidable, the statements that neither can be proven nor disproved in arithmetic. (Later, he also showed that the consistency of arithmetic can be formulated in arithmetic terms and therefore provides an example of such an undecidable statement. This is known as Gödel's second incompleteness theorem.)

Gödel presented his results at the Conference on Epistemology of the Exact Sciences on September 6, 1930. It appears that, except for John von Neumann, no one present (R. Carnap, H. Hahn, H. Reichenbach among others) grasped the significance of Gödel's talk. For the reader's benefit, Dawson gives a very clear exposition of Gödel's discoveries. By late November, von Neumann obtained an unprovability result of his own, only to find out that he was anticipated by Gödel by a few days. On several occasions thereafter, von Neumann lectured on Gödel's results rather than on his own. The story is most fascinating, as are many others in the book. If you want to learn more, you should probably do your own reading. Right now, I am concerned with a small detail to which the reader is treated at the beginning of the book.

Throughout his primary school career Gödel received the highest marks on all his subjects. The extent of drill work in arithmetic at his time can be gauged from a page from his first arithmetic workbook. A concept shines through that subtraction reverses the result of addition, but the exercise itself is pure rote — memorization by repetition — and would be frowned upon by most present day math educators. Nonetheless, I think the page might make a good poster for a mathematics class.

First, Kurt Gödel performed the exercise as a 6-7 year old child. At this age, kids love repetition, which for them is very much a conceptual activity. I believe it just can't be helped. Repetition and practice constitute an integral and necessary part of the learning process. Gödel did it...

Second, the poster may serve as a backdrop for introductory philosophical remarks about mathematics. Gödel has proven that not everything in mathematics is provable. By implication, one first conceives an idea, then proves it — if at all possible.

Third, it's OK to be mistaken. It's good to keep one's mind open while pursuing an idea. Who knows? The idea may metamorphose into its opposite as the result of one's efforts.

But let's return to repetition and practice. Are there repetitive activities that go beyond ("mindless" would be the usual adjective) memorization? Why, there's a great deal of them, of course. Repetition is a life line of computational mathematics. Iterative processes serve as one example.

Given a number and a set of rules to be performed that result in another number. Apply the rules to the new number and get a third one, and so on. Iterations may apply to a group of numbers or other mathematical objects. See, for example, the Candy game and Integer Iterations on a Circle. Following are three additional examples.

Start with a number and count the number E of even and the number O of odd digits [Ecker]. Write them down next to each other followed by their sum E + O. Treat the result as a new number and continue the process. In this example, the iterations converge very rapidly. In just a few steps they reach the number 123 which has exactly 3 digits of which 1 is even and two are odd. Therefore, applying the computations to 123 produces the number 123 itself, such that further iterations become really mindless. Of course we can always start with another number.

(In the applet below and other applets on this page, most of the numbers are clickable so that you can change their values. The starting number may be looked at as a string of individual digits or as a long number depending on whether the Autonomous digits button is checked or unchecked.)

The proof that the iterations always settle on the magic number 123 is simple but not exciting. Let's denote the above prescription applied to number n as f(n). If n has four digits, f(n) has three and may be only one of 044, 404, 134, 314, 224. If n has 5 digits, then f(n) still has 3 of them. The first time f(n) may have 4 digits is for n with at least 10 digits. This is also when f(n) may get 5 digits. The possibility of a 6 digit f(n) arises for numbers with at least 20 digits. Without formalizing the argument, it is clear that f(n) < n, for n with more than 3 digits. Among three digit numbers, there are only 033, 303, 123, and 213 to verify. For each of the four, f(n) = 123.

With the exception of bases 2, 3, and 4, the iterations always settle on number 123. In base 4, I could only find two terminating points: 1310 (1 + 3 = 4 in decimal) and 11011 (1 + 4 = 5). In base 3, there is only one: 10212 (3 + 2 = 5). In the binary system, there are only two points on which the iterations may possibly settle: 111101001 (3 + 6 = 9) and 1110111 (1 + 6 = 7). But there is a new phenomenon too. Some iterations enter a 2-cycle: f(1001101010) = 1011011010 (5 + 5 = 10 and 4 + 6 = 10), f(1011011010) = 1001101010.

We get more work intensive (but this is not the main point of course) iterations by summing up powers of digits [Ecker, Barbeau, p. 121]. In the decimal system, squaring of digits may only result in cycles. Raising digits to the third power and adding up leads to one of 5 points: 1, 153, 370, 371, 407. Modulo 3 those numbers are 1, 0, 1, 2, 2. All whole numbers divisible by 3 eventually settle on 153. Function f in this case has the property that it preserves the value modulo 3. For example, all iterates of a number equal 2 modulo 3 are equal 2 modulo 3. Far as I can judge, such numbers settle on either 371 or 407. On the other hand, there are cycles of numbers equal to 1 (mod 3). For example 2³ + 4³ + 4³ = 136, while 1³ + 3³ + 6³ = 244. Also f(160) = 217, f(217) = 352, and f(352) = 160, but there are more of them. Iterations that converge starting with numbers equal 1 (mod 3) settle on either 1 or 370.

Michael Ecker calls such points that terminate iterations black holes. They necessarily are fixed points of the corresponding function. The function f that is the sum of squares of the digits of a given number does not have a fixed point in base 10. In other bases, it may. For example, in base 3, f(12) = 12. In base 5, f(23) = 23. In general, for an odd base (2k - 1) we have f(k-1 k) = k-1 k (i.e., (k-1)(2k-1) + k = (k-1)² + k²). Similarly, f(k k) = k k.

All of the above iterative processes pose some problems. For example, which of the known fixed points are attractive and which are repelling, or whether it is possible (with the sum of the third powers) to differentiate between starting points that converge to 371 from those that converge to 407? I do not know how difficult those problems might be. But there is one curious problem that has been around from the 1930s that even Paul Erdös (1982) has judged as being too difficult for the present state of mathematics. It still is. The problem was proposed [Gardner, p. 203] by Lothar Collatz and is known as the Collatz Conjecture, but also as the 3X + 1 problem and is often associated with other names: Hailstone, Ulam, Syracuse.

Define f(n) = n/2 if n is even, and f(n) = 3n + 1, if n is odd. Collatz conjecture claims that regardless of the starting point the iterations settle eventually into a 3-cycle: 4, 2, 1, 4.

As a variant, an even number may be stripped entirely of its even factors (not just divided by 2) which leads to a shorter 2-cycle 4, 1, 4. For small numbers convergence is sufficiently fast to be observed even if calculations are carried by hand. The first number that takes more than 100 iterations is 27. Then such numbers become more frequent: 27, 31, 41, 47, 55, 62, ...

Well, let's sum up. Unlike first-order theories, the tool chest of a mathematics educator can never be complete. We should be always looking for novel ways to make practice more meaningful and less odious for students. Playful iterative processes are likely to fit the bill. Of the three discussed above, the first and the third may be offered even in elementary school; all are certainly suitable for middle school. Each provides an opportunity for practice but also for some investigations of substance. Quite a few patterns may be grasped from experimentation, some of which can be confirmed by rigorous reasoning, but not all. Students may be surprised to learn how easy it is at times to get to the front lines of modern mathematics.

References

1. E. J. Barbeau, Power Play, MAA, 1997
2. J. W. Dawson, Jr., Logical Dilemmas, A K Peters, 1997
3. M. W. Ecker, Number Play, Calculators, and Card Tricks: Mathemagical Black Holes, pp 41-52 in The Mathemagician and Pied Puzzler (E. Berlekamp and T. Rodgers, editors), A K Peters, 1999
4. M. Gardner, Wheels, Life, and Other Mathematical Amusements, W. H. Freeman. New York: 1983.

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com

Copyright © 1996-2001 Alexander Bogomolny