A few new facts about the EKG sequence
Piotr Hofman, Marcin Pilipczuk · 2008
The EKG sequence is defined as follows: a1 = 1, a2 = 2 and an is the smallest natural number satisfying gcd(an−1, an) > 1 not already in the sequence. The sequence was previously investigated by Lagarias, Rains and Sloane. In particular, we know that (an) is a permutation of the natural numbers and that the prime numbers appear in this sequence in an increasing order. Lagarias, Rains and Sloane performed many numerical experiments on the EKG sequence up to the 10 7 th term and came up with several interesting conjectures. This paper provides proofs for the core part of those conjectures. Namely, let (a ′ ) be the sequence (an) with all terms of the form p and 3p, for p prime, changed to 2p. First, we prove that for any odd prime an = p we have an−1 = 2p. Then we prove that limn→∞ a ′ n n = 1, i.e., we have an ∼ n except for the values of p and 3p for p prime: if an = p then an ∼ n , and if an = 3p then an ∼ 3n 2 .