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

           piotr.hofman@students.mimuw.edu.pl
         marcin.pilipczuk@students.mimuw.edu.pl

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→∞} \frac{a′_{n}}{n} = 1, i.e., we have a_{n} ∼ n except for the values of p and 3p for p prime: if a_{n} = p then a_{n} ∼ \frac{n}{2}, and if a_{n} = 3p then a_{n} ∼ \frac{3n}{2}.

1 Introduction

The EKG sequence is defined as follows: a_{1} = 1, a_{2} = 2 and a_{n} is the smallest natural number not already in the sequence satisfying gcd(a_{n−1}, a_{n}) > 1. It was originally defined by Ayres and later investigated by Lagarias, Rains and Sloane [1]. It appears as entry \underline{A064413} in the On-line Encyclopedia of Integer Sequences [4]. The first forty terms of the sequence are

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

Lagarias, Rains and Sloane [1] describe some basic properties of this sequence. In particular, they prove that it is a permutation of the natural numbers with linear asymptotic behavior; more precisely \frac{1}{260}n ≤ a_{n} ≤ 14n. We recall some of their lemmas and theorems in Section 3. Their numerical experiments resulted in several interesting conjectures. First, if a_{n} = p and p is a prime, then a_{n−1} = 2p, which we will prove in Section 4.2. Second, that a_{n} ∼ n except for when a_{n} = p is prime; then a_{n} = p ∼ \frac{n}{2} and a_{n+1} = 3p ∼ \frac{3n}{2}.

We will prove the conjectures mentioned above. To formulate what is proved let us introduce some notation. Let (z_{n}) be the inverse of the permutation (a_{n}), let (p_{i}) be the sequence of prime numbers in increasing order, and let (a′_{n}) be defined as follows: a′_{n} = 2p if a_{n} = 3p or a_{n} = p for p prime, a′_{n} = a_{n} otherwise. This definition was introduced by Lagarias, Rains and Sloane [1]. We prove that that lim_{n→∞} \frac{a′_{n}}{n} = 1. More precisely, we will prove that there exists a universal constant C such that for all natural numbers n we have

n − \frac{Cn}{log log log n} ≤ a_{n} ≤ n + \frac{Cn}{log log log n}.

Note that the speed of convergence is extremely slow. In particular, this result is weaker than a more precise conjecture made by Lagarias, Rains and Sloane [1] that a′_{n} ∼ n(1+ \frac{1}{3 log n}). In Section 5 we discuss some drawbacks and possible improvements of the proofs in this work.

In this work, we will use several strong results from number theory. These facts are gathered in Section 2.

In this work the letters c, C, C′, c′, C_{i}, c_{i} denote constants. If it is not specified otherwise, they are absolute numerical constants.

2 Number theory tools

Let us define p_{n} to be the n-th prime number and π(n) the number of primes smaller than n. According to Rosser [3], the following version of the prime number theorem holds:

Theorem 2.1. If n ≥ 55 then

π(n) < \frac{n}{log n − 4}.

We conclude that

Corollary 2.2. If n > 25000 > e^{10.1} then

π(n) < \frac{2n}{log n}

and

π(n) < \frac{n}{6} − 2

Let us now estimate the number of different prime divisors of n.

Lemma 2.3. Any natural number n has at most C \frac{log n}{log log n} different prime divisors.

Proof. If n has at least k prime divisors, then n ≥ 2 · 3 · · · · · p_{k} > k!, so by Stirling’s formula log n > C_{1}k log k. Let f(x) = C_{1}x log x. Then

f(C_{2} \frac{log n}{log log n}) = C_{1}C_{2} \frac{log n}{log log n}(log C_{2} + log log n − log log log n) > C_{3}C_{2} log n.

Therefore k < C_{4} \frac{log n}{log log n}.

The following is a well-known fact from calculus.

Theorem 2.4. Let p_{1}, p_{2}, … be the sequence of the prime numbers primes in increasing order (p_{1} = 2, p_{2} = 3, …). Then

∏_{n=1}^{∞} (1 − \frac{1}{p_{n}} ) = 0.

However, in our work we will need a stronger result; namely, Merten’s theorem [2].

Theorem 2.5. Let p_{1}, p_{2}, … be the sequence of prime numbers in increasing order (p_{1} = 2, p_{2} = 3, …). Then

lim_{n→∞}(log p_{n}) ∏_{n=1}^{∞} (1 − \frac{1}{p_{n}} ) = e^{−γ}

where γ is the Euler-Mascheroni constant.

Since p_{n} ∼ n log n the following is straightforward:

Corollary 2.6. There exists a universal constant C such that for all natural numbers n the following holds:

∏_{n=1}^{∞} (1 − \frac{1}{p_{n}} ) < \frac{C}{log n}.

Note: all results cited above are independent of the Riemann hypothesis.

3 Already known simple facts

As Lagarias, Rains and Sloane [1] defined, a prime dividing both a_{n−1} and a_{n} is called a controlling prime for a_{n}. Note that a controlling prime is not unique; if not specified otherwise, in proofs we choose any of the controlling primes. We will define g(n) = gcd(a_{n}, a_{n−1}). As observed by Lagarias, Rains and Sloane [1], we can define the sequence in a different way. For every prime p let B_{n}(p) be the smallest multiple of p that has not appeared in the first n terms of the sequence. Then a_{n+1} is smallest among all B_{n}(p) for primes p dividing a_{n}. The following lemmas and theorems were proved by Lagarias, Rains and Sloane [1] and for some of them we quote the proofs, since they are quite basic and will be important in the next section.

Lemma 3.1. Let p > 2 be a prime. If a_{n} is the first term divisible by p, then a_{n+1} = p and a_{n} = pq where q is the smallest prime divisor of a_{n−1}.

Proof. For any k | a_{n−1} the number kp is a good candidate for a_{n}, so a_{n} = qp, where q is the smallest possible controlling prime, i.e., the smallest prime divisor. Since q is a controlling prime, q, 2q, …, q(p − 1) were already used. So if q was a controlling prime for a_{n+1}, then a_{n+1} ≥ q(p + 1) > p, where p is a good candidate. So p will be a controlling prime and a_{n+1} = p.

Lemma 3.2. The prime numbers appear in a_{n} in increasing order.

Proof. If a_{n+1} = p, then a_{n} = qp is the first term divisible by p. For any p′ < p we have qp′ < qp = a_{n}, so the term qp′ appeared in the sequence earlier.

Lemma 3.3. If {m, 2m, …, km} ⊂ {a_{i} : 1 ≤ i ≤ M}, then {1, 2, …, k} ⊂ {a_{i} : 1 ≤ i ≤ M + 1}.

Proof. By induction on k. For k = 1 it is obvious, since a_{1} = 1. Let {m, 2m, …, km} ⊂ {a_{i} : 1 ≤ i ≤ M}. Let a_{n} = km, n ≤ M. Let q be a controlling prime for a_{n}. If q | m, then all the numbers m, 2m, …, (k − 1)m were good candidates for a_{n}, so they were before a_{n}, so, by the induction hypothesis, {1, 2, …, k − 1} ⊂ {a_{i} : i ≤ n}. The number k is a great candidate for a_{n+1}, because all smaller numbers were used, so {1, 2, …, k} ⊂ {a_{i} : i ≤ n+1}. If q | k, then k was a candidate for a_{n}, so it was before a_{n}. By the induction hypothesis {1, 2, …, k − 1} ⊂ {a_{i} : i ≤ M + 1}. This completes the proof.

Lemma 3.4. For any prime p, the numbers 1, 2, … p−1 appear in the EKG sequence before p.

Proof. As in the proof of Lemma 3.1, before a_{n+1} = p for p prime, there was a_{n} = qp and all the numbers q, 2q, …, q(p − 1) were used before. Therefore, by Lemma 3.3, all the numbers 1, 2, …, p − 1 were before p.

Theorem 3.5. For all n the EKG sequence satisfies the following inequality

\frac{1}{260}n < a_{n} < 14n.

Corollary 3.6. If for some a, b, we have z_{a} < z_{b} then a < 14z_{a} < 14z_{b} < 14 · 260b.

4 New results

4.1 The fundamental lemma

Most of the proofs in this paper are based on the following observation.

Lemma 4.1. Fix any real number x. Then for every prime q there can be at most one index n for which q is a controlling prime for a_{n} and a_{n−1} < x ≤ a_{n}.

Proof. According to the definition, a_{n} is the smallest multiple of q not yet used in the sequence. Since a_{n} ≥ x, all multiples of q smaller than x were already used, and later in the sequence there is no term divisible than q smaller than x, i.e., if k > n and q | a_{k}, then a_{k} ≥ x.

This lemma has important consequences; it strongly limits the number of times the sequence can cross the border of x going upwards. Since all the primes in the sequence appear in increasing order, if p_{k+1} has not yet appeared, one can cross the border of x upwards only k = π(p_{k+1}) = Θ(\frac{p_{k+1}}{log p_{k+1}} ) times.

4.2 2p is before p

In this section we will prove that each odd new prime in the EKG sequence is introduced by a subsequence 2p, p, 3p. We will simply use Lemma 4.1 and the estimate for π(x).

We will prove the following theorem:

Theorem 4.2. For any primes p, q > 2 the term qp appears in the sequence after 2p.

Proof. We will prove Theorem 4.2 by contradiction. Let us assume that p is the first prime such that for some N we have a_{N+1} = p and a_{N} = qp, where q > 2. From Lemmas 3.1 and 3.2 we know that these are the first terms divisible by p and previous terms of the sequence are divisible only by smaller primes than p. From Lemma 4.1 we know that before the term a_{N} the sequence can cross the border of 2p upwards only π(p) times — for every prime smaller than p at most once. Now we will show that for large p, the sequence must have crossed this border downwards Θ(p) times, which is asymptotically bigger than π(p). We will try to be tight on the constants, to match the numerical experiments made by Lagarias, Rains and Sloane [1], and therefore the theorem will be proved for the whole sequence.

Since q is the controlling prime for a_{N} = qp, all multiples of q — {q, 2q, …, (p−1)q} have appeared before the term a_{N}. Particularly important for us are numbers greater than 2p and divisible by 2q, because if a_{k} is such a number for k < N then there is the possibility that a_{k+1} = 2p. This cannot hold for k ≤ N, so for every such a_{k} the next number is smaller than 2p. Among the terms \{q, 2q, …, (p − 1)q\} there are at least ⌊\frac{qp−2p}{2q}⌋ ≥ ⌊\frac{p}{6}⌋ = Θ(p) numbers both divisible by 2q and greater than 2p. They all appeared in the sequence before a_{N}. So we have at least ⌊\frac{p}{6}⌋ moments before a_{N}, where the sequence goes downwards through the border 2p and, due to Lemma 4.1, at most π(p) moments before a_{N}, where the sequence goes upwards.

From Theorem 2.2 we know that if p > 25000 we have π(p) < ⌊\frac{p}{6}⌋ − 1. The number of upward and downward crossing should differ by at most 1, so we have a contradiction for p > 25000.

Lagarias, Rains and Sloane [1] computed the first 10 000 000 terms of the sequence. The last prime number not greater than 25 000 is 24 989 and it appears around the 50 000-th term. Up to this bound all primes p were preceded by the term 2p. Therefore the theorem is proved for the whole sequence.

From this the following theorem is an obvious corollary:

Theorem 4.3. If a_{n} = p and p > 2 is prime, then a_{n−1} = 2p.

Proof. From Lemma 3.1 we know that a_{n−1} = qp for some prime q and this is the first term divisible by p. Therefore q = 2, since 2p could not have appeared before.

The above idea can be generalized. As in the proof of Theorem 4.2 we can use any natural number n instead of p and any fixed number a instead of 2. This leads to the following theorem, which we do not use later, but which is an interesting result on its own. This theorem could also be deduced from the final theorem — lim_{n→∞} \frac{a′_{n}}{n} = 1, but the proof based on the proof of Theorem 4.2 is much more elementary. We do not include the proof here, since it is very similar to the proof of Theorem 4.2.

Theorem 4.4. Let a > 1 be a natural number. Then there exists a natural number N such that for all natural numbers b > a and n > N the term an appears in the sequence before bn, i.e., z_{an} < z_{bn}. In particular, this holds if log N > Ca^{3} for some universal constant C.

Lemma 4.1 can be somewhat enhanced, since we know that 2p appears before every odd prime p, and there 3p appears afterward. The following lemma shows that the moments when the sequence crosses the border x upwards and it is not the EKG tick (i.e., in the subsequence of the form q, 3q for q prime) are very rare.

Lemma 4.5. Let x > 1 be a real number and let B be the set

B = {n : a_{n} < x ≤ a_{n+1}; a_{n} is not a prime}.

Then |B| ≤ π(\sqrt{x}).

Proof. Let n ∈ B. Since a_{n} is composite, it has a prime divisor not greater than \sqrt{a_{n}}, which is smaller than \sqrt{x}. Let q be any such prime divisor.

Since a_{n+1} ≥ x and all multiples of q are candidates for a_{n+1}, all multiples of q smaller than x must have been used before. Therefore, after a_{n}, there are no free multiples of q smaller than x. So every n ∈ B uses at least one prime q smaller than \sqrt{x} — there are no more unused multiples of q smaller than x, so |B| ≤ π(\sqrt{x}).

4.3 Numbers above the border

By Lemma 4.1, we know that the sequence can cross the border of an integer x upwards at most π(x) times. The interesting question now is: before an integer x appears in the sequence, how many terms greater than x can appear?

Now we are giving partial answer to that question. We need to assume that x has got some small divisor, so the numbers greater than x having a common divisor with x (i.e., such terms, after which x is a candidate for the next term) are quite dense.

The following lemma will be used later only for a being a small prime different than 3 and while reading one can think of a as such number — much smaller than n and prime.

Lemma 4.6. Let a > 1 be an integer. Then there are at most Ca\frac{an}{log log an} ≤ Ca^{2} \frac{n}{log log n} terms of the EKG sequence greater than an and appearing before an, where C is a universal constant.

Proof. Fix a > 1 and large n and let N = z_{an}, i.e., a_{N} = an. Let A = {1 ≤ i < N : a_{i} > an}; we need to estimate |A|. From Lemma 4.1 we know that the sequence can cross the border of an upwards at most π(an) times. We will consider several cases.

Let A_{1} = {i ∈ A : a | a_{i}}. If i ∈ A_{1}, then an is a candidate for a_{i+1}, so after such i the sequence goes downwards through the border of an if i+1 < N. Therefore |A_{1}| ≤ π(an)+1.

Now let i ∈ A \ A_{1} and let q be a controlling prime for a_{i}. The idea now is as follows: either a_{i} is quite close to the border an, or there is an already used multiple of qa below a_{i}. The formal argument follows.

Note that Corollary 3.6 implies q ≤ a_{i} ≤ C_{0} · an for some universal constant C_{0}.

Let f(s) = a_{i} − sq. Note that gcd(q, a) = 1, because otherwise an would be a better candidate for a_{i}. For all s (if f(s) > 0) f(s) was already used in the sequence before a_{i}. Among f(1), f(2), …, f(a − 1) there is exactly one f(s_{0}(a_{i})), such that a | f(s_{0}(a_{i})).

Let A_{2} = {i ∈ A \ A_{1} : f(s_{0}(a_{i})) ≤ an}. For every prime q there are at most a − 1 such numbers a_{i}, for which q is a controlling prime and i ∈ A_{2} — these are the first at most a − 1 multiples of q greater than an. Therefore |A_{2}| ≤ (a − 1)π(C_{0}an) ≤ C′_{0}(a − 1)π(an).

Let A_{3} = A \ A_{1} \ A_{2} = {i ∈ A \ A_{1} : f(s_{0}(a_{i})) > an}. The term f(s_{0}(a_{i})) was used before a_{i}, thus for some j < i we have a_{j} = f(s_{0}(a_{i})) and obviously j ∈ A_{1}. For how many indices i′ can we have f(s_{0}(a_{i′})) = a_{j}? For every prime divisor r of a_{j}, at most a − 1 times: a_{i′} can be one of the numbers a_{j} + r, a_{j} + 2r, …, a_{j} + (a − 1)r. According to Lemma 2.3, the number a_{j} can have at most C_{1} \frac{log a_{j}}{log log a_{j}} distinct prime divisors.

According to Corollary 3.6 we have a_{j} < 14 · 260an, so a_{j} can have at most C_{2} \frac{log(an)}{log log(an)} distinct prime divisors, where C_{2} is a universal constant.

Therefore

|A_{3}| ≤ |A_{1}| · (a − 1) · C_{2} \frac{log(an)}{log log(an)}.

Since π(an) ≤ C \frac{an}{log(an)} for some universal constant C, we have

|A| = |A_{1}| + |A_{2}| + |A_{3}| ≤ π(an) + C′_{0}(a − 1)π(an) + C_{2}(a − 1)π(an)\frac{log(an)}{log log(an)} ≤

≤ Ca\frac{an}{log log an} ≤ Ca^{2} \frac{n}{log log n}.

The following theorem is an obvious corollary:

Theorem 4.7. There exists a universal constant C such that for every integer a > 1 the following holds: z_{an} ≤ an + Ca\frac{an}{log log an} ≤ an + Ca^{2} \frac{n}{log log n}.

Proof. Fix a > 1. From Lemma 4.6 we know that there are at most Ca\frac{an}{log log an} indices i < z_{an} such that a_{i} > an. Obviously there are at most an indices i < z_{an} for which a_{i} ≤ an. Therefore there are at most an + Ca\frac{an}{log log an} = an + o(n) indices i < z_{an}.

However, Lemma 4.6 is not sufficient for all our purposes. It limits the number of terms greater than an, but does not limit how big the terms are. The following lemma is an improvement to Lemma 4.6. It uses almost the same technique, but the proof is more complicated and we will use the enhanced version of Lemma 4.1, i.e., Lemma 4.5 and Lemma 4.6 itself.

Lemma 4.8. Let a > 1 be an integer not divisible by 3 and let \frac{1}{3} > ε > 0. Then there exists an integer N(a) such that for all integers n > N(a) if the number x > (a + 2ε)n appeared in the sequence before term an, then x is of the form 3p for some prime p. In particular, the sufficient condition is that log log N(a) > \frac{Ca^{2}}{ε} for some universal constant C.

Proof. First, due to Lemma 4.6, we know that there are at most C_{1}a\frac{an}{log log(an)} terms greater than an before the term an appears in the sequence. Choose N(a) so big, that for all n > N(a) we have C_{1}a\frac{an}{log log an} < 1 + \frac{εn}{3}, i.e., there are more numbers divisible by 3 in the segment (an, (a + ε)n) than terms of the sequence greater than an before an appears. Note that this one holds if log log N(a) > \frac{C_{2}a^{2}}{ε}.

For such a big n, whenever any term of form 3p appears in the sequence before the term an appears, there is an unused divisible by three candidates for the next term smaller than (a + ε)n. So the next term will be smaller than the border of (a + ε)n.

From Lemma 4.5, there are at most π(\sqrt{(a + ε)n}) indices i smaller than z_{an}, for which a_{i} < (a + ε)n, and a_{i+1} ≥ (a + ε)n and a_{i} is composite. In the other case, if a_{i} < (a + ε)n and a_{i+1} ≥ (a + ε)n and a_{i} is prime, the next term a_{i+2} will be smaller than (a + ε)n.

Suppose there is an index i < z_{an} for which a_{i} is composite and a_{i+1} > (a+2ε)n. Let i be the first such index. Since a_{i} ≤ (a + 2ε)n, a_{i} has a prime divisor q smaller than \sqrt{(a + 2ε)n}. If a_{i+1} is greater than (a + 2ε)n, then all multiples of q in the segment ((a + ε)n, (a + 2ε)n) must have been used before. In this segment there are at least ⌊\frac{ε}{aq}n⌋ numbers divisible by both q and a. Let us call such terms interesting ones. All interesting terms were used before an appears in the sequence. Therefore after such an interesting term, number an is good candidate for the next term, so after such terms the sequence goes downwards through the border of (a + ε)n — the next term will be at most an.

Moreover, since any interesting term is divisible by a, it is not of the form of 3p for some prime p, since p ≥ \frac{an}{3} > a and a is not divisible by 3.

Except for the ticks of the form p, 3p, the sequence went upwards through the border of (a + ε)n at most π(\sqrt{(a + ε)n}) times, so there can be at most π(\sqrt{(a + ε)n}) interesting terms, i.e., from the segment ((a + ε)n, (a + 2ε)n) divisible by aq. But for large n we have

\frac{ε}{aq} n ≥ \frac{ε}{a\sqrt{2 + 2ε}}\sqrt{n} > π(\sqrt{(a + ε)n}),

since π(x) = Θ(\frac{x}{log x}). Note that this inequality holds if log n > \frac{C_{3}a^{\frac{3}{2}}}{ε} for some universal constant C_{3}. This condition is much weaker than the bound log log n > \frac{C_{2}a^{2}}{ε} we assumed earlier.

Therefore if log log n > \frac{C_{2}a^{2}}{ε} the only terms greater than (2 + 2ε)n are of the form 3p for p prime.

While analyzing the EKG sequence one question appears very often. Let us fix an integer a > 1, and let a be not divisible by 3 (in fact, the most interesting case is when a is a prime different than 3). Imagine the term an has appeared in the sequence; the question is, what is the smallest k such that ak has yet not appeared in the sequence (i.e., before an)? Lemma 4.9, which is in fact a simple corollary of Lemma 4.8, provides an answer to that question.

Lemma 4.9. Let a > 1 be an integer not divisible by 3. Let m_{a}(n) be smallest k, such that term ak has not appeared in the first n terms of the sequence. Let M_{a}(n) be the biggest k such that term ak has appeared in the first n terms of the sequence. Then

lim_{n→∞} \frac{M_{a}(n) − m_{a}(n)}{n} = 0.

More precisely, there exists a universal constant C such that the following holds:

M_{a}(n) − m_{a}(n) ≤ \frac{Can}{log log n}.

Proof. For large n we can apply Lemma 4.8 for ε = \frac{C_{1}a^{2}}{log log n} obtaining that aM_{a}(n) ≤ (a + 2ε)m_{a}(n). Keeping in mind that, according to Lagarias, Rains and Sloane [1], the EKG sequence has linear bounds, (i.e., ci < a_{i} < Ci for some constants c, C, so both M_{a}(n) → ∞ and m_{a}(n) → ∞ with n → ∞ and m_{a}(n) ≤ Cn + a), and that ε → 0 as n → ∞, we have for sufficiently large n:

M_{a}(n) − m_{a}(n) < \frac{2ε}{a}m_{a}(n) < \frac{C_{1}a^{2}}{a log log n}(Cn + a) < \frac{C_{2}an}{log log n}.

4.4 Linear limit for even terms

In this section we will prove that lim_{n→∞} \frac{2n}{z_{2n}} = 1, i.e., that an even term 2n is at position approximately 2n. This will give us a skeleton for proving that all the terms x except for p and 3p are at position approximately x.

From Theorem 4.7 for a = 2 we know that term z_{2n} ≤ 2n + C \frac{n}{log log n}, which gives us lim inf_{n→∞} \frac{2n}{z_{2n}} ≥ 1. What we need to prove is that z_{2n} ≥ 2n − o(n). We will try to estimate the asymptotic behavior of the o(n) part in the proof.

Theorem 4.10.

lim sup_{n→∞} \frac{2n}{z_{2n}} ≤ 1.

Moreover, there exists a universal constant C such that

z_{2n} ≥ 2n − \frac{Cn}{log log log n}.

Proof. Fix a small ε < \frac{1}{7}. We will prove, that for large n, namely log log log n > \frac{C}{ε}, z_{2n} ≥ (2 − 6ε)n. This will lead to the result.

First, from Lemma 4.9, we can assume that n is sufficiently large, so that all even numbers smaller than (2 − ε)n were already used in the sequence before the term 2n. For this we need only log log n > \frac{C}{ε}, which is one log weaker than the assumption made in this theorem.

Let p_{1}, p_{2}, … be a sequence of the prime numbers in increasing order (p_{1} = 2 and p_{2} = 3). By Merten’s theorem (Theorem 2.5 and Corollary 2.6)

∏_{n=1}^{K} (1 − \frac{1}{p_{n}} ) < \frac{C}{log K} .

Let K be sufficiently large (namely log K > \frac{C}{ε}) such that

∏_{n=3}^{K} (1 − \frac{1}{p_{n}} ) < ε.

Notice, that we omitted p_{1} = 2 and p_{2} = 3 in this product.

Let P = ∏_{n=3}^{K} p_{i}. Since p_{i} ≤ Ci log i,

P ≤ (CK log K)^{K} ≤ (CK)^{2K} ≤ e^{\frac{2C}{ε} e^{\frac{C}{ε}}} ≤ e^{e^{\frac{C′}{ε}}} .

Therefore log log P ≤ \frac{C}{ε}. Since we assumed that log log log n > \frac{C}{ε}, we can assume that n > \frac{P}{ε} + P by choosing appropriate universal constants.

Let us concentrate on numbers smaller than (2−3ε)n, not divisible by any of the numbers p_{3}, p_{4}, …, p_{K}. Let s = ⌊\frac{(2−3ε)n}{P}⌋ > \frac{1}{ε}. Then in every segment (iP, (i+1)P] for i = 0, 1, …, s− 1 there are exactly P · ∏_{i=3}^{K}(1 − \frac{1}{p_{i}}) < P ε numbers not divisible by any p_{3}, p_{4}, …, p_{K}. So in [1, (2 − 3ε)n] there are at most sP ε + ((2 − 3ε)n − sP) < 2nε + P < 3εn numbers not divisible by any of p_{3}, p_{4}, …, p_{K}.

Since n > \frac{P}{ε} + P, then n > \frac{2p_{K}}{ε}. Then, since all even numbers smaller than (2 − ε)n appear in the sequence before index z_{2n}, for all 3 ≤ i ≤ K some number divisible by 2p_{i} greater than (2 − 2ε)n appears in the sequence before index z_{2n}. Now we are going to use Lemma 4.9 to estimate, that for all 3 ≤ i ≤ K all numbers divisible by p_{i} smaller than (2 − 3ε)n were used in the sequence before the term 2n. Let 3 ≤ i ≤ K. To use Lemma 4.9, we need \frac{Cp_{i}n}{log log n} < εn. However, p_{i} ≤ p_{K} ≤ CK log K < e^{\frac{C′}{ε}}, so we need to prove that

\frac{Ce^{\frac{C′}{ε}}}{ε} < log log n. By applying logarithm to both sides we get \frac{C′′}{ε} < log log log n, which was our assumption.

But, as we proved before, there are at most 3εn numbers not divisible by any of the p_{3}, p_{4}, …, p_{K} smaller than (2 − 3ε)n. In total, there are at most (3ε + 3ε)n = 6εn numbers smaller than 2n, than might not have been used in the sequence before index z_{2n}. Therefore, for large n, z_{2n} > (2 − 6ε)n, which completes the proof.

Corollary 4.11.

lim_{n→∞} \frac{2n}{z_{2n}} = 1.

More precisely, there exists a universal constant C such that for all n:

2n − \frac{Cn}{log log log n} ≤ z_{2n} ≤ 2n + \frac{Cn}{log log n}.

Since for every prime p > 3, we have z_{p} = z_{2p} + 1 = z_{3p} − 1, and from Corollary 4.11, lim_{i→∞} \frac{2p_{i}}{z_{2p_{i}}} = 1, the following corollary is obvious:

Corollary 4.12.

lim_{i→∞} \frac{p_{i}}{z_{p_{i}}} = \frac{1}{2}

lim_{i→∞} \frac{3p_{i}}{z_{3p_{i}}} = \frac{3}{2}

From Corollary 4.11 we can conclude a few other facts that can be useful in our final proof.

Corollary 4.13. Let x > 0. Then there exists a universal constant C such that all even terms smaller than x appear in the EKG sequence before index x + \frac{Cx}{log log x}.

Corollary 4.14. Let x > 0. Then there exists a universal constant C such that all even terms greater than x + \frac{Cx}{log log log x} appear in the sequence after index x.

Proof. This is straightforward corollary from Corollary 4.11 — if 2n > x + \frac{Cx}{log log log x} then z_{2n} > 2n − \frac{C′n}{log log log n} > x by adjusting the constant C.

4.5 Linear limit for all terms

In this final section we will prove that if (e_{i}) is a sequence of all odd natural numbers except these of the form 3p and p for p prime, in increasing order, then lim_{i→∞} \frac{e_{i}}{z_{e_{i}}} = 1. This, together with linear bounds proved by Lagarias, Rains and Sloane [1] and Corollary 4.11, gives us the desired result: lim_{n→∞} \frac{a′_{n}}{n} = 1.

First we will prove that any e_{i} could not appear in the sequence too early, i.e., it can appear at position e_{i} −o(e_{i}). This will be a quite straightforward corollary from Corollary 4.12: if some e_{i} appears, there must have been a not much smaller even term before.

Later, we will prove that e_{i} could not appear in the sequence too late, i.e., it can appear at position e_{i} + o(e_{i}). In this proof once again we will be estimating how many times do the sequence cross some border upwards or downwards. We will prove, that not much bigger even term was not used before the term e_{i}.

Theorem 4.15.

lim sup_{i→∞} \frac{e_{i}}{z_{e_{i}}} ≤ 1.

More precisely, there exists a universal constant C such that for all e_{i}

z_{e_{i}} ≥ e_{i} − \frac{Ce_{i}}{log log log e_{i}} .

Proof. Fix i and let n = z_{e_{i}}, i.e., a_{n} = e_{i}. Since e_{i} is not of the form of p or 3p, then a_{n−1} is composite. Lagarias, Rains and Sloane [1] proved that a_{n−1} < 14(n−1) < 14n < 14·260a_{n} = 14 · 260e_{i}. Therefore a_{n−1} has a prime divisor q satisfying q ≤ \sqrt{a_{n−1}} < \sqrt{14 · 260e_{i}}. Since a_{n} = e_{i}, all multiples of q smaller than e_{i} must have been used in the sequence before the term a_{n}. Let x(i) be biggest integer divisible by 2q smaller than e_{i}. Since q | x(i), z_{x(i)} < n. Obviously x(i) ≥ e_{i} − 2q > e_{i} − 2\sqrt{14 · 260}\sqrt{e_{i}}. But x(i) is even, so from Corollary 4.11 we have z_{x(i)} ≥ x(i) − \frac{Cx(i)}{log log log x(i)} for some universal constant C. Therefore

z_{e_{i}} = n > z_{x(i)} ≥ x(i) − \frac{Cx(i)}{log log log x(i)} > e_{i} − C\sqrt{e_{i}} − \frac{Ce_{i}}{log log log e_{i}} ≥ e_{i} − \frac{C′e_{i}}{log log log e_{i}} .

Theorem 4.16.

lim inf_{i→∞} \frac{e_{i}}{z_{e_{i}}} ≥ 1.

More precisely, there exists a universal constant C such that for all e_{i}

z_{e_{i}} ≤ e_{i} + \frac{Ce_{i}}{log log log e_{i}} .

Proof. We will prove the theorem by contradiction. Assume there exists an increasing unbounded sequence 0 < c_{0} < c_{i} → ∞ such that for all I there exists i > I such that z_{e_{i}} > (1 + 7ε_{i})e_{i} where ε_{i} = \frac{c_{i}}{log log log e_{i}}. We can assume that ε_{i} < \frac{1}{7}, i.e., c_{i} ≤ \frac{1}{7} log log log e_{i}. Let e_{i} be a very large term satisfying z_{e_{i}} > (1 + 7ε_{i})e_{i}.

We will start by using Corollaries 4.13 and 4.14 several times. We can use them since

lim sup_{i→∞} \frac{\frac{c_{i}}{log log log e_{i}}}{\frac{C}{log log log e_{i}}} = ∞ and \frac{C}{log log log e_{i}} is the worst asymptotic bound in Corollaries 4.13

and 4.14.

First, using Corollary 4.13 we can assume that e_{i} is large enough so that all even terms smaller than e_{i} appeared before index (1 + ε_{i})e_{i}. In other words, for all 2n < e_{i} we have z_{2n} < (1 + ε_{i})e_{i}.

Second, using Corollary 4.13 a second time, we can assume that e_{i} is large enough so that all even terms smaller than (1 + 6ε_{i})e_{i} have appeared before index (1 + 7ε_{i})e_{i}. In other words, for all 2n < (1 + 6ε_{i})e_{i} we have z_{2n} < (1 + 7ε_{i})e_{i} < z_{e_{i}}.

Third, using Corollary 4.14 we can assume that e_{i} is large enough so that all even terms greater than (1 + 2ε_{i})e_{i} have appeared after index (1 + ε_{i})e_{i}. In other words, for all 2n > (1 + 2ε_{i})e_{i} we have z_{2n} > (1 + ε_{i})e_{i}.

To sum up, we have an interval of indices (i.e., a part of sequence) between (1 + ε_{i})e_{i} and (1 + 7ε_{i})e_{i}, where all even terms between (1 + 2ε_{i})e_{i} and (1 + 6ε_{i})e_{i} appear and no even term smaller than e_{i} appear. Let us call these even terms between (1 + 2ε_{i})e_{i} and (1 + 6ε_{i})e_{i} the important terms.

Since e_{i} is composite, it has prime divisor q(i) not greater than \sqrt{e_{i}}. Therefore, among all important terms, we have at least

⌊\frac{4ε_{i}e_{i}}{2q(i)}⌋ ≥ ⌊2ε_{i}\sqrt{e_{i}}⌋ ≥ ε_{i}\sqrt{e_{i}} ≥ \frac{c_{0}\sqrt{e_{i}}}{log log log e_{i}}

terms divisible by q(i). Let us call these terms very important ones.

Every very important term is not of the form 2p for p > 3 prime, since it is divisible by 2q(i) and greater than 2q(i). And obviously after every very important term the number e_{i} is a candidate for the next term. Therefore we have at least \frac{c_{0}\sqrt{e_{i}}}{log log log e_{i}} moments between indices (1+ε_{i})n and (1+7ε_{i})n, when the EKG sequence crosses the border of e_{i} downwards. Notice, that none of these moments are subsequences of the form 2p, p, since a very important term is not of the form 2p.

From Lemma 4.5 we know, that before index z_{e_{i}} the EKG sequence can cross the border of e_{i} upwards at most π(\sqrt{e_{i}}) times, except for the subsequences of the form p, 3p for p prime.

Let us look at the subsequence p, 3p for p prime that appeared in the EKG sequence after index (1 + ε_{i})e_{i} and before index (1 + 7ε_{i})e_{i}. The term before was obviously 2p and, since every even term smaller than e_{i} has appeared before index (1 + ε_{i})e_{i}, we have that 2p > e_{i}, except for maybe one moment where z_{2p} = ⌊(1+ε_{i})e_{i}⌋. Otherwise we have p < e_{i} < 2p < 3p, so the EKG sequence crossed here the border of e_{i} first downwards and then upwards.

Therefore between indices (1 + ε_{i})e_{i} and (1 + 7ε_{i})e_{i} the number of times the sequence crosses the border of e_{i} upwards and downwards, without taking into account subsequences of the form 2p, p and p, 3p for p prime, should differ by at most two. The other ones just form pairs — subsequences of the form 2p, p, 3p with p < e_{i} < 2p < 3p. But we proved that we have at least \frac{c_{0}\sqrt{e_{i}}}{log log log e_{i}} downward crossings and at most π(\sqrt{e_{i}}) = O(\frac{\sqrt{e_{i}}}{log e_{i}}) upward crossings, which is a contradiction. This completes the proof.

To sum up, in the end, we have proved the following theorem, by Theorems 4.15, 4.16 and Corollaries 4.11 and 4.12:

Theorem 4.17.

lim_{n→∞} \frac{a′_{n}}{n} = 1.

More precisely, there exists a universal constant C such that

n − \frac{Cn}{log log log n} ≤ a′_{n} ≤ n + \frac{Cn}{log log log n}.

5 Conclusion

In this paper we presented a quite elementary proof that in the EKG sequence odd primes appear in the subsequences 2p, p, 3p (Theorem 4.3) and, building some technical tools on top of observation made in Lemma 4.1 and Lemma 4.5, we managed to prove asymptotic behavior of the EKG sequence, namely, that lim_{n→∞} \frac{a′_{n}}{n} = 1. We tried to estimate the speed of the convergence through the proofs to see if we could use these techniques to cope with the stronger conjecture made by Lagarias, Rains and Sloane [1]:

Conjecture 5.1 (Lagarias, Rains, Sloane).

a′_{n} ∼ n(1 + \frac{1}{3 log n}).

The proved result, Theorem 4.17, is far from this goal. We were able to prove a very weak convergence speed — \frac{C}{log log log n} tail. This is the reason we were not able to apply any argument similar to those supporting Conjecture 5.1. Let us repeat the argument. In the EKG sequence integers appear more or less in the increasing order, except for terms of the form p and 3p. If a_{n} = m, then earlier in the sequence we had all integers smaller than m except for numbers of the form p and 3p smaller than m, but we had all p and 3p for 2p ≤ m. This leads to the Conjecture 5.1 by

n ∼ m − π(m) − π(\frac{m}{3}) + 2π(\frac{m}{2}) ∼ m − \frac{m}{3 log m}.

Unfortunately, in this argument we need to investigate sets of missing terms (numbers of the form p and 3p) that are of the size \frac{Cn}{log n}. Such sizes are lost comparing to \frac{Cn}{log log log n} part. Moreover, in this paper we get weaker convergence speed (\frac{Cn}{log log n}) very early, namely in the Lemma 4.6, so we were not able to use this technique.

To get closer to proving Conjecture 5.1 using techniques presented in this paper, one needs to improve the convergence speed. Note that there are two places where we gain one more log in the speed. One is Lemma 4.6, where we need to multiply π(x) by the number of different prime divisors of x, which might be \frac{log x}{log log x}. The proof of Lemma 4.6 is quite tricky and we were not able to improve it.

The second place where we lose out is the proof of Theorem 4.10, probably the most technical proof in this paper. The estimations made there are quite rough, therefore we think they might be somehow improved. However, we do not know how to do it now.

To sum up, although this paper provides some new tools and techniques to cope with the EKG sequence, and proves the core part of the conjectures made by Lagarias, Rains and Sloane [1], there is still quite a significant hole between what is done and what is conjectured. The aforementioned Conjecture 5.1 seems to us to be the most interesting question remaining.

Acknowledgments

We would like to say a huge “thank you” to few our professors and colleagues, without whom this work wouldn’t exist. Chronologically first, to Professor Jaroslaw Grytczuk and to Andrzej Grzesik for showing us the EKG sequence. Later, to our RPG Fellowship, Marek Grabowski, Kaja Malek, Michal Pilipczuk and Jakub Wojtaszczyk, for patience in listening to our proofs and concepts instead of playing Earthdawn. Finally, to Joanna Jaszunska and Jakub Wojtaszczyk for pointing out many errors and an almost infinite number of missing articles in the paper. And finally, to Professor Jerzy Urbanowicz, for being our mentor while working on this problem.

References

[1] J. C. Lagarias, E. M. Rains, and N. J. A. Sloane. The EKG sequence. Experimental Math., 11 (2002), 437–446.

[2] F. Mertens. Ein Beitrag zur analytischen Zahlentheorie. J. reine angew. Math., 78 (1874), 46–62.

[3] B. Rosser. Explicit bounds for some functions of prime numbers. American J. Math., 63 (1941), 211–232.

[4] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences.

   http://www.research.att.com/~njas/sequences/.

2000 Mathematics Subject Classification: Primary 11B83. Keywords: EKG sequence, integer sequence, prime numbers.

(Concerned with sequence \underline{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.