Some Properties of a Sequence Defined with the Aid of Prime Numbers

Brăduţ Apostol

“Spiru Haret” Pedagogic High School

5 Timotei Cipariu St.

620004 Focşani

Romania apo brad@yahoo.com

Laurenţiu Panaitopol^{1}

Lucian Petrescu “Henri Coandă” Technical College

2 Tineretului St. 820235 Tulcea

Romania

petrescuandreea@yahoo.com

László Tóth Department of Mathematics

University of Pécs Ifjúság útja 6 7624 Pécs Hungary

ltoth@gamma.ttk.pte.hu

1Deceased.

Abstract

For every integer n ≥ 1 let a_{n} be the smallest positive integer such that n + a_{n} is prime. We investigate the behavior of the sequence (a_{n})_{n≥1}, and prove asymptotic results for the sums ∑_{n≤x} a_{n}, ∑_{n≤x} 1/a_{n}, and ∑_{n≤x} log a_{n}.

1 Introduction

For every integer n ≥ 1 let a_{n} be the smallest positive integer such that n + a_{n} is prime. Here a_{1} = 1, a_{2} = 1, a_{3} = 2, a_{4} = 1, a_{5} = 2, a_{6} = 1, a_{7} = 4, etc. This is sequence \underline{A013632} in Sloane’s Online Encyclopedia of Integer Sequences [4]. For n ≥ 2, a_{n} is the smallest positive integer such that gcd(n!, n + a_{n}) = 1. In this paper we study the behavior of the sequence (a_{n})_{n≥1}, and prove asymptotic results for the sums ∑_{n≤x} a_{n}, ∑_{n≤x} 1/a_{n} and ∑_{n≤x} log a_{n}.

We are going to use the following standard notation:

• π(x) is the number of primes ≤ x,

• π_{2}(x) is the number of twin primes p, p + 2 such that p ≤ x,

• p_{n} is the n-th prime,

• d_{n} = p_{n+1} − p_{n},

• f(x) ≪ g(x) means that |f(x)| ≤ Cg(x), where C is an absolute constant,

• g(x) ≫ f(x) means that f(x) ≪ g(x),

• f(x) = F (x) + O(g(x)) means that f(x) − F (x) ≪ g(x),

• f(x) ≍ g(x) means that cf(x) ≤ g(x) ≤ Cf(x) for some positive absolute constants c and C,

• f(x) ∼ g(x) means that lim_{x→∞} f(x)/g(x) = 1. We will apply the following known asymptotic results concerning the distribution of the

primes:

π(x) ∼ \frac{x}{log x}, p_{n} ∼ n log n (Prime number theorem),
∑_{p_{n}≤x} d_{n}^{2} ≪ x^{23/18+ε} for every ε > 0 (unconditional result of Heath-Brown [1]), (1)

∑_{p_{n}≤x} d_{n}^{2} ≪ x(log x)^{3} (assuming the Riemann hypothesis, result of Selberg [3]), (2)

(\frac{d_{2}d_{3} ⋯ d_{n}}{(log 2)(log 3) ⋯ (log n)})^{1/n} ≍ 1 (due to Panaitopol [2, Prop. 3]).  (3)

This research was initiated by Laurenţiu Panaitopol (1940–2008), former professor at the Faculty of Mathematics, University of Bucharest, Romania. The present paper is dedicated to his memory.

2 Equations and identities

By the definition of a_{n}, for every n ≥ 1 we have n + a_{n} = p_{π(n)+1}, that is

a_{n} = p_{π(n)+1} − n.  (4)

From (4) we deduce that for every k ≥ 1,

a_{p_{k}} = p_{k+1} − p_{k}, a_{p_{k}+1} = p_{k+1} − p_{k} − 1, …, a_{p_{k+1}−1} = 1.  (5)

Proposition 1. For every integer a ≥ 1 the equation a_{n} = a has infinitely many solutions.

Proof. Let A_{k} = {1, 2, …, p_{k+1} − p_{k}}. Since lim sup_{k→∞}(p_{k+1} − p_{k}) = ∞, it follows from (5) that for every integer a ≥ 1 there exist infinitely many integers k ≥ 1 such that a ∈ A_{k}, whence the equation a_{n} = a has infinitely many solutions.

Now we compute the sum S_{n} = ∑_{i=1}^{n} a_{i}.

Proposition 2. For every prime n ≥ 3 we have

S_{n} = \frac{1}{2} (2p_{π(n)+1} − p_{π(n)} + ∑_{k=1}^{π(n)−1} d_{k}^{2}) ,  (6)

and for every composite number n ≥ 4,

S_{n} = \frac{1}{2} (p_{π(n)}^{2} + 2(n + 1 − p_{π(n)})p_{π(n)+1} + ∑_{k=1}^{π(n)−1} d_{k}^{2} − n^{2} − n) .  (7)

Proof. If n ≥ 3 is a prime, then n = p_{m} for some m ≥ 2. By using (4),

S_{n} = ∑_{i=1}^{n} (p_{π(i)+1} − i)

= 2 + 3 + (5 + 5) + ⋯ + (p_{m} − p_{m−1})p_{m} + p_{m+1} − \frac{n(n + 1)}{2}

= 2 + ∑_{k=2}^{m} p_{k}(p_{k} − p_{k−1}) + p_{m+1} − \frac{n(n + 1)}{2}

= \frac{1}{2} (p_{1}^{2} + 2 ∑_{k=2}^{m} p_{k}^{2} − 2 ∑_{k=2}^{m} p_{k}p_{k−1} + 2p_{m+1} − n^{2} − n)

= \frac{1}{2} (2p_{m+1} − n + ∑_{k=1}^{m−1}(p_{k+1} − p_{k})^{2})

and (6) follows by using that m = π(n).

Now let t ≥ 4 be composite. Let m ≥ 2 be such that p_{m} < t < p_{m+1}. By applying (6) for n = p_{m}, where m = π(n) = π(t), we deduce

S_{t} = S_{n} + ∑_{i=n+1}^{t} a_{i} = S_{n} + ∑_{i=n+1}^{t} (p_{π(i)+1} − i)

= \frac{1}{2} (2p_{π(t)+1} − p_{π(t)} + ∑_{k=1}^{π(t)−1}(p_{k+1} − p_{k})^{2}) + \frac{(2p_{π(t)+1} − n − t − 1)(t − n)}{2}

= \frac{1}{2} (2p_{π(t)+1} − p_{π(t)} + ∑_{k=1}^{π(t)−1}(p_{k+1} − p_{k})^{2} + 2p_{π(t)+1}(t − n) − t^{2} − t + n^{2} + n)

= \frac{1}{2} (p_{π(t)}^{2} + 2(t + 1 − p_{π(t)})p_{π(t)+1} + ∑_{k=1}^{π(t)−1}(p_{k+1} − p_{k})^{2} − t^{2} − t)

and (7) is proved.

Remark 3. If n is prime, then (7) reduces to (6). Therefore, the identity (7) holds for every integer n ≥ 3.

Next we compute the product P_{n} = ∏_{i=1}^{n} a_{i}.

Proposition 4. For every prime n ≥ 3 we have

P_{n−1} = ∏_{k=1}^{π(n)−1} d_{k}!,  (8)

and for every composite number n ≥ 4,

P_{n−1} = ∏_{k=1}^{π(n)−1} d_{k}! ∏_{k=1}^{n−p_{π(n)}}(p_{π(n)+1} − p_{π(n)} − k + 1).  (9)

Proof. Let n = p_{m} ≥ 3 be a prime. By using (5),

P_{n−1} = ∏_{i=2}^{m}(p_{i} − p_{i−1})! = ∏_{i=1}^{m−1}(p_{i+1} − p_{i})!,

which proves (8).

Now let t ≥ 4 be composite such that p_{m} < t < p_{m+1}. By applying (8) for n = p_{m}, where m = π(n) = π(t), we deduce

P_{t−1} = P_{n−1} ∏_{i=n}^{t−1} a_{i} = P_{n−1} ∏_{i=n}^{t−1} (p_{π(i)+1} − i)

= ∏_{k=1}^{π(t)−1} d_{k}! ∏_{j=1}^{t−p_{m}} (p_{m+1} − p_{m} − j + 1)

= ∏_{k=1}^{π(t)−1} d_{k}! ∏_{k=1}^{t−p_{π(t)}} (p_{π(t)+1} − p_{π(t)} − k + 1)

and (9) is proved.

Remark 5. If n is prime, then the second product in (9) is empty and (9) reduces to (8). Hence the identity (9) holds for every integer n ≥ 3.

3 Asymptotic results

Theorem 6. For every ε > 0,

x log x ≪ ∑_{n≤x} a_{n} ≪ x^{23/18+ε},  (10)

where 23/18 ≐ 1.277. If the Riemann hypothesis is true, then the upper bound in (10) is x(log x)^{3}.

Proof. Let x ≥ 2 and let p_{k} ≤ x < p_{k+1}. By using (6) for n = p_{k+1},

∑_{n≤x} a_{n} ≤ ∑_{i=1}^{p_{k+1}} a_{i} = \frac{1}{2} (2p_{k+2} − p_{k+1} + ∑_{i=1}^{k} d_{i}^{2})

≪ p_{k+2} + ∑_{p_{i}≤x} d_{i}^{2}.

Taking into account the estimate (1) due to Heath-Brown, and the fact that p_{k+2} ∼ p_{k} ≤ x we get the unconditional upper bound in (10). If the Riemann hypothesis is true, then by using Selberg’s result (2) we obtain the upper bound x(log x)^{3}.

Now, for the lower bound we use the trivial estimate

∑_{p_{n}≤x} d_{n}^{2} ≫ x log x,

which follows from the inequality between the arithmetic and quadratic means. We deduce that

∑_{n≤x} a_{n} ≥ ∑_{i=1}^{p_{k}} a_{i} = \frac{1}{2} (2p_{k+1} − p_{k} + ∑_{i=1}^{k−1} d_{i}^{2})

≫ ∑_{p_{i}≤p_{k−1}} d_{i}^{2} ≫ p_{k−1} log p_{k−1} ∼ x log x,

since p_{k−1} ∼ k log k and k = π(x) ∼ x/ log x, log k ∼ log x.

To prove our next result we need the following

Lemma 7. We have

∑_{2≤n≤x} log d_{n} = x log log x + O(x).  (11)

Proof. The inequalities (3) can be written as

cn < ∑_{i=2}^{n} log d_{i} − ∑_{i=2}^{n} log log i < Cn

for some positive absolute constants c and C. Now (11) emerges by applying the well known asymptotic formula

∑_{2≤n≤x} log log n = x log log x + O(x).

Theorem 8. We have

∑_{n≤x} \frac{1}{a_{n}} = \frac{x log log x}{log x} + O (\frac{x}{log x}) .  (12)

Proof. For x = p_{m} − 1 (m ≥ 2) we have by (5),

∑_{n≤p_{m}−1} \frac{1}{a_{n}} = 1 + ∑_{i=2}^{m} (1 + \frac{1}{2} + ⋯ + \frac{1}{p_{i} − p_{i−1}} ) .

For an arbitrary x ≥ 3 let p_{k} (k ≥ 2) be the prime such that p_{k} ≤ x < p_{k+1}. Using the familiar inequalities

log m < 1 + \frac{1}{2} + ⋯ + \frac{1}{m} ≤ 1 + log m (m ≥ 1)

we deduce

log(p_{i} − p_{i−1}) < 1 + \frac{1}{2} + ⋯ + \frac{1}{p_{i} − p_{i−1}} ≤ 1 + log(p_{i} − p_{i−1}) (i ≥ 2)

and

1 + ∑_{i=2}^{k} log(p_{i} − p_{i−1}) + \frac{1}{d_{k}} < ∑_{n≤p_{k}−1} \frac{1}{a_{n}} + \frac{1}{a_{p_{k}}}

≤ ∑_{n≤x} \frac{1}{a_{n}} ≤ ∑_{n≤p_{k+1}−1} \frac{1}{a_{n}} ≤ 1 + k + ∑_{i=2}^{k+1} log(p_{i} − p_{i−1}).

By (11) we obtain

∑_{n≤x} \frac{1}{a_{n}} = k log log k + O(k),

Here k = π(x) ∼ x/ log x, log k ∼ log x and we deduce (12).

Theorem 9. One has

x ≪ ∑_{n≤x} log a_{n} ≪ x log x.

Proof. For an arbitrary x ≥ 3 let p_{k} (k ≥ 2) be the prime such that p_{k} ≤ x < p_{k+1}. Using the elementary inequalities

m log m − m + 1 ≤ log m! ≤ m log m (m ≥ 1)

we deduce by applying (8) that

∑_{n≤x} log a_{n} ≤ ∑_{n≤p_{k+1}−1} log a_{n} = ∑_{i=1}^{k} log d_{i}! ≤ ∑_{i=1}^{k} d_{i} log d_{i}

< ∑_{i=1}^{k} d_{i} log p_{i} < (log p_{k}) ∑_{i=1}^{k} d_{i} < (log p_{k})p_{k+1},

where we also used that d_{i} = p_{i+1} − p_{i} < p_{i} by Chebyshev’s theorem. Here

p_{k} ∼ k log k, k = π(x) ∼ x/ log x, log k ∼ log x,  (13)

and we obtain the upper bound x log x.

On the other hand,

∑_{n≤x} log a_{n} > ∑_{n≤p_{k}−1} log a_{n} = ∑_{i=1}^{k−1} log d_{i}!

> ∑_{i=1}^{k−1}(d_{i} log d_{i} − d_{i} + 1) = ∑_{i=2}^{k−1} d_{i} log d_{i} − p_{k} + k + 1.

Here

∑_{i=2}^{k−1} d_{i} log d_{i} = ∑_{\begin{matrix}i=2 \\ d_{i}≥3 \end{matrix}}^{k−1} d_{i} log d_{i} + 2 log 2 ∑_{\begin{matrix}i=2 \\ d_{i}=2 \end{matrix}}^{k−1} 1

≥ (log 3) ∑_{\begin{matrix}i=2 \\ d_{i}≥3 \end{matrix}}^{k−1} d_{i} + (2 log 2)π_{2}(k − 1)

= (log 3) (∑_{i=2}^{k−1} d_{i} − ∑_{\begin{matrix}i=2 \\ d_{i}=2 \end{matrix}}^{k−1} d_{i}) + (2 log 2)π_{2}(k − 1)

= (log 3) (p_{k} − p_{2} − 2π_{2}(k − 1)) + (2 log 2)π_{2}(k − 1) = (log 3)p_{k} − 2 log(3/2)π_{2}(k − 1) − 3 log 3 > (log 3)p_{k} − 2 log(3/2)k − 3 log 3,

where it is sufficient to use the obvious estimate π_{2}(k − 1) < k. Note that log 3 ≐ 1.09, 2 log(3/2) ≐ 0.81, 3 log 3 ≐ 3.29.

We deduce that

∑_{n≤x} log a_{n} > 0.09p_{k} − 3.

Now (13) gives the lower bound x.

References

[1] D. R. Heath–Brown, The differences between consecutive primes, III, J. London Math. Soc. (2) 20 (1979), 177–178.

[2] L. Panaitopol, Properties of the series of differences of prime numbers, Publ. Centre de Rech. Math. Pures Neuchâtel (Serie 1) 31 (2000), 21–28.

[3] A. Selberg, On the normal density of primes in small intervals, and the difference between consecutive primes, Arch. Math. Naturvid. 47 (1943), No. 6, 87–105.

[4] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. http://oeis.org.

2010 Mathematics Subject Classification: Primary 11A41; Secondary 11N05. Keywords: prime numbers, difference of consecutive primes, asymptotic behavior.

(Concerned with sequences \underline{A000040}, \underline{A001223}, \underline{A013632}, and \underline{A076821}.)

Received March 3 2015; revised version received April 3 2015. Published in Journal of Integer Sequences, May 21 2015.

Return to Journal of Integer Sequences home page.