EKG Sequence
I overheard two nerds in the computer lab talking about a recent contest to generate the first N terms of this function in the shortest time possible.
The EKG sequence is the integer sequence having 1 as its first term, 2 as its second, and with each succeeding term being the smallest number not already used that shares a factor with the preceding term. This results in the sequence 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, … (Sloane’s A064413). When plotted as a connect-the-dots plot (left figure), the sequence looks somewhat like an electrocardiogram (abbreviated “EKG” in medical circles), so this sequence became known as the EKG sequence. Lagarias et al. have computed the first 10 million terms of the sequence. Every term appears exactly once in this sequence, and the primes occur in increasing order.