Journal of Integer Sequences, Vol. 11 (2008), Article 08.4.2

A Few New Facts about the EKG Sequence


Piotr Hofman and Marcin Pilipczuk
Department of Mathematics, Computer Science and Mechanics
University of Warsaw
Warsaw
Poland

Abstract:

The EKG sequence is defined as follows: $a_1=1$, $a_2=2$ and $a_n$ is the smallest natural number satisfying $\gcd (a_{n-1}, a_n) > 1$ not already in the sequence. The sequence was previously investigated by Lagarias, Rains and Sloane. In particular, we know that $(a_n)$ 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_n')$ be the sequence $(a_n)$ with all terms of the form $p$ and $3p$, for $p$ prime, changed to $2p$. First, we prove that for any odd prime $a_n = p$ we have $a_{n-1}=2p$. Then we prove that $\lim_{n\to\infty} \frac{a_n'}{n} = 1$, i.e., we have $a_n \sim n$ except for the values of $p$ and $3p$ for $p$ prime: if $a_n = p$ then $a_n \sim \frac{n}{2}$, and if $a_n = 3p$ then $a_n \sim \frac{3n}{2}$.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A064413 .)

Received March 4 2008; revised version received September 20 2008. Published in Journal of Integer Sequences, October 2 2008.

Return to Journal of Integer Sequences home page