The EKG Sequence

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 330,000 other sequences of interest to mathematicians are cataloged in Neil J.A. Sloane's On-Line Encyclopedia of Integer Sequences.

Here's an example discovered in 2001 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 by Jonathan Ayres, and it 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.

A plot of the first 72 terms of the EKG sequence.

Intrigued by this combination of disorder and regularity, Sloane, Jeffrey C. Lagarias, and Eric M. Rains 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 2002 paper 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.

Originally posted April 8, 2002