Ivars Peterson's MathTrek
April 8, 2002
Sequences of numbers have long fascinated both amateur and professional mathematicians. Many people are familiar with the Fibonacci sequence, in which each new term is the sum of the previous two terms: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on. More than 69,000 other sequences of interest to mathematicians are catalogued in Neil J.A. Sloane's On-Line Encyclopedia of Integer Sequences at http://www.research.att.com/~njas/sequences/.
Here's a recently discovered example that has prompted some serious mathematical investigation.
The first term is 1 and the second is 2. Each succeeding term is the smallest number not already used that shares a factor with the preceding term. So, the third term must be 4 (2 and 4 have the common factor 2), the fourth term 6 (4 and 6 have the common factor 2), the fifth term 3 (6 and 3 have the common factor 3), and the sixth term 9 (6 is already used, so the next available number that shares a factor with 3 is 9).
SEQUENCE: 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27, 30, 25, 35, 28, 26, 13, 39, 36, 32, 34, 17, 51, 42, 38, 19, 57, 45, 40, 44, 46, 23, 69, 48, 50, 52, 54, 56, 49, 63, 60, 55, 65, 70, 58, 29, 87, 66, 62, 31, 93, 72, 64, 68, 74, 37, 111, 75, 78, 76, 80, 82, and so on.
The sequence was discovered last year by Jonathan Ayres, and it now appears as entry A064413 in Sloane's encyclopedia.
When plotted, the sequence of numbers looks somewhat like an electrocardiogram, or EKG, so it was dubbed the EKG sequence. Interestingly, although relatively short segments of the sequence appear to behave erratically, a plot of the first 10,000 or so terms shows considerable regularity.
Intrigued by this combination of disorder and regularity, Sloane, Jeffrey C. Lagarias, and Eric M. Rains of AT&T Labs-Research in Florham Park, N.J., decided to see what they could find out about the sequence's mathematical properties.
"The EKG sequence has a simple recursive definition, yet seems surprisingly difficult to analyze," the researchers noted in a preprint describing their findings. "Its definition combines both additive and multiplicative aspects of the integers, and the 'greedy' property of its definition produces a complicated dependence on the earlier terms of the sequence."
Despite such difficulties, the mathematicians succeeded in demonstrating that the sequence contains all positive integers--something that is not immediately obvious. Moreover, every number appears exactly once, so the EKG sequence is a permutation of the positive integers. At the same time, the primes appear in ascending order.
Lagarias and his colleagues worked out an efficient way to generate the EKG sequence and computed 10 million terms. Trends apparent in these data suggested several conjectures. For instance, whenever a prime p occurs in the sequence, it is preceded by 2p and followed by 3p.
"Although it is theoretically possible that some other multiple of p occurs before p (for example, we might have seen . . ., 3p, p, 2p, . . .), this does not appear in the first 107 terms," the researchers observed.
In general, however, "there remains a large gap between what is conjectured and what is proved," the mathematicians cautioned. And there remains much territory for numerical exploration.
Copyright 2002 by Ivars Peterson
Lagarias, J.C., E.M. Rains, and N.J.A. Sloane. Preprint. The EKG sequence. Available at http://xxx.lanl.gov/abs/math.NT/0204011.
Peterson, I. 2001. Fibonacci's Chinese calendar. MAA Online (Feb. 5).
Sloane, N.J.A., and S. Plouffe. 1995. The Encyclopedia of Integer Sequences. San Diego, Calif.: Academic Press. See also Sloane's On-Line Encyclopedia of Integer Sequences at http://www.research.att.com/~njas/sequences/.
Comments are welcome. Please send messages to Ivars Peterson at firstname.lastname@example.org.
A collection of Ivars Peterson's early MathTrek articles, updated and illustrated, is now available as the MAA book Mathematical Treks: From Surreal Numbers to Magic Circles.