Solution: ‘Be Still My Pulsating Sequence’

Why does the sequence of numbers in the above chart resemble the characteristic spiky, periodic pulsations of an electrocardiograph? This sequence, as I mentioned in this month’s Insight puzzle, is not present in Neil Sloane’s famous Online Encyclopedia of Integer Sequences (OEIS), which catalogs all the interesting integer sequences discovered to date. Our puzzle asked:

Question 1:

Consider the sequence of numbers shown below:

13    26    2      4     6     3      9     12     8     10     5     15     18     14      7      21      24      16 …

Unlike most mathematical functions, this sequence, graphed in the picture above, spikes up and down like the pulsations of the heart. Can you figure out the simple rule behind it?

To generate the sequence, start with 13. Every subsequent number is the smallest number higher than 1 that shares a common factor with the last number, and has not occurred in the sequence so far. Thus, the smallest number that shares a common factor with 13 is 26, which is therefore in the second place; next comes 2, which is the smallest factor of 26 that has not yet occurred; and so on. Here’s how it looks if we continue the sequence:

13, 26, 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, 32, 34, 17, 51, 36, 38, 19, 57, 39, 42, 40, 44, 46, 23, 69, 45, 48, 50 …

As diligent Quanta readers discovered, this sequence is a variant of the OEIS sequence number A064413, which is, in fact, known as the EKG sequence because of its resemblance to an electrocardiogram. It is defined as: a(1) = 1; a(2) = 2; for n > 2, a(n) = the smallest number not already used that shares a factor with a(n – 1). The EKG sequence goes:

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 …

Our sequence becomes identical to the EKG sequence at the 44th step (on the number 48). The OEIS sequence A169857 shows how long a variant sequence takes to merge with A064413 if you start with x instead of 2. So while our declaration about the sequence’s nonexistence in the OEIS was factually correct, the canonical sequence is, in fact, part of the OEIS. How could it not be?

Concerning the eventual merging of our sequence with the parent sequence, Neil Sloane said there is a “lovely unsolved problem”:

Show that no matter which number you start with (using the same generating rule), the resulting sequence eventually joins the EKG sequence A064413. It would be really great if one of your readers could find a proof of that. It is a question that has been unsolved for a long time.

Now there’s a challenge that might spur an ambitious Quanta reader to achieve OEIS immortality!

Could there be other rules that fit the 18 numbers we originally presented? Of course there could, as several readers pointed out. As I mentioned, this is an inductive problem where we are trying to find a rule or hypothesis that fits the numbers given. This is very similar to what scientists do when they try to find regularities, rules and laws in nature. The problem in both cases is that we have finite data, and therefore hundreds or thousands of rules can fit. This concern, known as “underdetermination,” was best articulated by John Stuart Mill in A System of Logic:

Most thinkers of any degree of sobriety allow, that an hypothesis … is not to be received as probably true because it accounts for all the known phenomena; since this is a condition sometimes fulfilled tolerably well by two conflicting hypotheses; … while there are probably a thousand more which are equally possible, but which, for want of anything analogous in our experience, our minds are unfitted to conceive.

What do we do, then? In science, the final arbiter is more data points. But we also have to make a choice regarding which hypothesis we choose to follow if we don’t want to waste our whole lives testing thousands of hypotheses. Here, as in science, we look for rules that are elegant: simple, compact and without too many arbitrary or free parameters. Very often these kinds of rules do indeed work in nature — and in puzzles not designed by sadists! I gave you my reason for why they work in nature in last month’s solution: I believe that evolution has hard-wired Occam’s razor in our brains, and the gradual increase in the complexity of the universe from simple beginnings also makes such elegant patterns more likely in nature.

I commend readers who found the actual EKG sequence rule, as well as others who came up with their own rules, such as Ravi Kumar Meduri and Gaurish Korpal. You can see, however, that Gaurish’s original and interesting idea of power-of-two “checkpoints” is not as compact as the actual rule. Unfortunately, it fails for the next checkpoint when we add more points, but oddly, it succeeds for the one after that in the EKG sequence. A valiant attempt!

Question 2:

Do you think that every positive integer greater than 1 will appear in this sequence, or will some integers be skipped? Can you prove your answer?

Yes, every positive integer greater than 1 will appear. The time-honored mathematical method for such proofs is the mathematical principle of reductio ad absurdum — you assume the opposite of what you are trying to prove, and show that it leads to an absurd result. Therefore, the opposite of our assumption, which is the proposition to be proved, has to be true.

Reader Daniel McLaury showed that, if you assume that some number n > 1 is missing from the sequence, it requires many other numbers to also be missing. Specifically, there would be only a finite number of multiples of small primes, and no instances of primes that were greater than a certain size. Therefore, the sequence would be comprised of finitely many multiples of finitely many primes, and would therefore be finite. But this is impossible, because of the way the sequence was defined — given a number that is currently at the “end” of the sequence, we can always find an arbitrarily large number which shares a prime factor with it. The sequence is therefore infinite. This contradiction implies that our assumption was wrong, and therefore every integer greater than 1 must appear as a term of the sequence.

You can check Daniel’s complete proof in the comments.

The paper “The EKG Sequence” by J.C. Lagarias, E.M. Rains and N.J.A. Sloane gives a proof in formal mathematical language. This proof starts by proving and building on an interesting property of the EKG sequence — the fact that the prime numbers occur strictly in increasing order (they represent the lowest points of the “EKG spikes”).

Question 3:

How far down the sequence do you have to go to encounter a pair of adjacent numbers that share more than one prime factor?

Again, here’s Daniel McLaury:

Terms 575–580 of the sequence are …, 608, 589, 620, 610, 614, 307, … Notice that 620 and 610 share a factor of ten [and therefore have two common prime factors, 2 and 5].

I am not aware of a simpler way to discover that 620 and 610 are the first pair of such numbers than to just work your way that far into the sequence. Fortunately, this isn’t too hard these days if you know computer programming. Notice that you could choose between two different sequence rules at this point, allowing or disallowing double prime factors in adjacent terms. In the absence of a compelling reason, most mathematicians would consider the rejection of double factors to be arbitrary and therefore inelegant.

Question 4:

Why on earth does this sequence begin with the number 13? (Outlandish reasons are encouraged!)

Many readers figured out that this was because 13 is the smallest number we could have used to start a variant EKG sequence that does not appear in the OEIS, and hence could not be found by a simple OEIS lookup. As usual, Quanta readers were too smart to be fazed by that!

Thank you all for contributing. The Quanta T-shirt for this month goes to Daniel McLaury for his original proof and his correct answers to all the other questions. Congratulations to Daniel, and a very happy Thanksgiving to all.