On a Recursively Defined Sequence Involving the Prime Counting Function

Altug Alkan

Graduate School of Science and Engineering

Piri Reis University Istanbul Turkey

altug.alkan@pru.edu.tr

Andrew R. Booker School of Mathematics University of Bristol

Woodland Road Bristol, BS8 1UG United Kingdom

andrew.booker@bristol.ac.uk

Florian Luca School of Mathematics

University of the Witwatersrand

Private Bag X3, Wits 2050 Johannesburg South Africa

Research Group in Algebraic Structures and Applications

King Abdulaziz University

Jeddah Saudi Arabia

Centro de Ciencias Matemáticas UNAM Morelia Mexico

Florian.Luca@wits.ac.za

Abstract

We prove some properties of sequence \underline{A335294} from the On-Line Encyclopedia of Integer Sequences, defined by

a_{n} = π(n) − π(∑_{k=1}^{n−1} a_{k}),

where π(x) is the number of primes ≤ x. In particular we show that the sequence (a_{n})

assumes every non-negative integral value infinitely often.

1 Introduction

Let π(x) = #{p prime : p ≤ x} denote the prime counting function. In this paper we consider the sequence (a_{n})_{n≥1} defined by

a_{n} = π(n) − π(∑_{k=1}^{n−1} a_{k}) for n ≥ 1.

Apart from a difference in the first three terms, this is sequence \underline{A335294} in the OEIS,^{1} and its initial terms are

0, 1, 2, 0, 1, 1, 1, 1, 0, 0, 1, 1, 2, 1, 1, 0, 1, 1, 2, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 2, 2, 1,
1, 0, 0, 1, 1, 1, 1, 2, 1, 2, 2, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 0, 0,
1, 1, 1, 1, 2, 1, 2, 2, 1, 0, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, …

A brief examination reveals that the sequence is not monotonic and displays a remarkably slow rate of growth. In this direction, see Table 1, which shows the smallest solutions to a_{n} = k for each k ≤ 13. (This is a subsequence of the prime numbers for k ≥ 1; note that for k ∈ {3, 4, 5, 6, 9, 10, 13} the corresponding n is also the larger of a twin prime pair.)

\begin{matrix}k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n & 1 & 2 & 3 & 229 & 3259 & 15739 & 449569 \\ k & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ n & 6958841 & 130259903 & 2404517671 & 56014949761 & 538155413969 & 21692297487587 & 21692297487589 \end{matrix}

Table 1: Smallest n satisfying a_{n} = k, cf. \underline{A335337}

Let s_{n} denote the summatory sequence,

s_{n} = ∑_{k=1}^{n} a_{k} for n ≥ 0.

1Sequence \underline{A335294} imposes the initial condition a_{1} = 1, whereas we adopt the convention that the empty sum is 0, so that a_{1} = π(1) − π(0) = 0. We prefer this convention since it is more elegant and simplifies some proofs. As we show in Section 3, the sequence is eventually stable under any perturbation of the initial terms, so this is not a significant alteration.

Our main result establishes some distributional properties of (a_{n})_{n≥1} and (s_{n})_{n≥0}. In order to state them, we define g(x) to be the maximum distance between a real number y ≤ x and the largest prime p ≤ y, i.e.,

g(x) = sup_{y∈[2,x]} min{y − p : p ≤ y} for x ≥ 2.

Note that g is a continuous, piecewise linear, non-decreasing function, and

π(n) − π(n − g(n) − 1) ≥ 1 for all integers n ≥ 2.

Conjecturally one has g(x) = O(log^{2} x); the best result to date, due to Baker, Harman, and Pintz [2], is that g(x) ≤ x^{21/40} for all sufficiently large x.

Theorem 1. The following conclusions hold:

(i) a_{n} ≥ 0 and a_{n} − max{1, 2π(a_{n})} ≤ a_{n+1} ≤ a_{n} + 1 for all n ≥ 1;

(ii) a_{n} = O(\sqrt{g(n)/ log g(n)}) for all n ≥ 5;

(iii) for each k ≥ 0, there are infinitely many n such that a_{n} = k;

(iv) n − g(n) ≤ s_{n} ≤ n − 2 for all n ≥ 9;

(v) s_{n} = n − g(n) for infinitely many n.

Proof. We begin with the upper estimate in (iv). Suppose that s_{n} ≤ n holds for some n ≥ 0; note that this is the case for n = 0. By definition we have

s_{n+1} = s_{n} + a_{n+1} = s_{n} + π(n + 1) − π(s_{n}),  (1)

so that

n + 1 − s_{n+1} = (n + 1 − s_{n}) − (π(n + 1) − π(s_{n})).  (2)

Since s_{n} ≤ n, the right-hand side is non-negative, and in fact it counts the number of nonprime integers in the interval (s_{n}, n+1]. Hence we have s_{n+1} ≤ n+1. By induction it follows that s_{n} ≤ n for all n ≥ 0.

Next we improve this to s_{n} ≤ n − 2. Suppose n ≥ 9 is such that s_{n+i} ≤ n + i − 2 for i ∈ {0, 1, 2, 3}; we verify this directly for n = 9. If s_{n+4} ≥ n + 3 then we have

n + 4 − s_{n+4} ≤ 1 ⟹ (s_{n+3}, n + 4] contains at most one composite number

⟹ n + 2 and n + 4 are prime

⟹ n + 3, n + 1, n and n − 1 are composite ⟹ s_{n+3} ≥ n + 1 ⟹ n + 3 − s_{n+3} ≤ 2 ⟹ (s_{n+2}, n + 3] contains at most two composite numbers ⟹ s_{n+2} ≥ n ⟹ n + 2 − s_{n+2} ≤ 2 ⟹ (s_{n+1}, n + 2] contains at most two composite numbers ⟹ s_{n+1} ≥ n − 1 ⟹ n + 1 − s_{n+1} ≤ 2 ⟹ (s_{n}, n + 1] contains at most two composite numbers ⟹ s_{n} ≥ n − 1.

This contradicts the assumption that s_{n} ≤ n−2, so we must have s_{n+4} ≤ n+2. By induction it follows that s_{n} ≤ n − 2 for all n ≥ 9.

Next, for all n ≥ 1 we have

a_{n} = π(n) − π(s_{n−1}) ≥ π(n) − π(n − 1) ≥ 0.  (3)

It follows that s_{n} is non-decreasing, and thus

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

Moreover, by Montgomery and Vaughan’s upper estimate [8, Corollary 2] for primes in short intervals, we have

a_{n+1} ≥ a_{n} − (π(s_{n−1} + a_{n}) − π(s_{n−1})) ≥ a_{n} − max{1, 2π(a_{n})}.

This proves (i). We also note that the lower estimate can be improved to a_{n+1} ≥ a_{n} − π(a_{n}) for n ≥ 4 and 2 ≤ a_{n} ≤ 1731, by work of Gordon and Rodemich [6].

Let n be a natural number satisfying

s_{n} ≥ n − g(n).  (5)

Note that this holds for n = 3. If s_{n} ≥ n + 1 − g(n + 1) then

s_{n+1} ≥ s_{n} ≥ n + 1 − g(n + 1).

Otherwise we have n − g(n) ≤ s_{n} ≤ n − g(n + 1), so that

s_{n+1} = s_{n} + π(n + 1) − π(s_{n}) ≥ n − g(n) + π(n + 1) − π(n − g(n + 1)).

By the definition of g we have π(n + 1) − π(n − g(n + 1)) ≥ 1, so

s_{n+1} ≥ n + 1 − g(n) ≥ n + 1 − g(n + 1).

Thus, in either case, (5) holds with n replaced by n+1. By induction, (5) holds for all n ≥ 3, and this completes the proof of (iv).

Turning to (ii), let n be a natural number, and suppose that k = a_{n} ≥ 3. Applying (4) inductively, we see that

a_{n−i} ≥ k − (π(n) − π(n − i)) for all i < n.  (6)

Let h ≥ 2 be the largest integer such that π(h) ≤ k/3. Taking i = n − 1 in (6) we see that π(n) ≥ k ≥ 3π(h) > π(h), whence h < n. Moreover, by the prime number theorem we have h ≍ k log k. By [8, Corollary 2], for any non-negative integer i ≤ h we have

π(n) − π(n − i) ≤ max{1, 2π(i)} ≤ 2π(h) ≤ 2k/3,

so that a_{n−i} ≥ k/3. Therefore,

s_{n} − s_{n−h} = ∑_{i=0}^{h−1} a_{n−i} ≥ \frac{hk}{3} ≫ k^{2} log k.

By (iv), s_{n} − s_{n−h} = h + O(g(n)) ≪ k log k + g(n). Thus, k^{2} log k ≪ k log k + g(n), and (ii) follows.

Next, let p, q be a pair of consecutive odd primes attaining a maximal prime gap. Define sequences (s′_{n})_{n≥p} and (d_{n})_{n≥p} by

s′_{p} = p,  s′_{n+1} = s′_{n} + π(n + 1) − π(s′_{n}) for n ≥ p,  (7)

and

d_{n} = s′_{n} − s_{n} for n ≥ p.

Subtracting (7) and (1), we find that

d_{n+1} = d_{n} − (π(s_{n} + d_{n}) − π(s_{n})) for n ≥ p.

It follows that 0 ≤ d_{n+1} ≤ d_{n}, so that s_{n} ≤ s′_{n} for all n ≥ p. From (7) we see that s′_{p+1} = s′_{p+2} = ⋯ = s′_{q−1} = p. Hence

q − 1 − s_{q−1} ≥ q − 1 − s′_{q−1} = q − 1 − p = g(q − 1),

and by (iv) it follows that s_{q−1} = q − 1 − g(q − 1). This proves (v).

(Moreover we have s_{q−1} = p, s_{q} = p + 1, s_{q+1} = p + 2, and if p > 3 then

max{s_{n} : s_{n} < p} = p − 1;

thus s_{n} + h is infinitely often prime for each h ∈ {−2, −1, 0, 1}. By the estimate of Ford et al. on large prime gaps [4], we also see that n − s_{n} ≫ \frac{log n log log n log log log log n}{log log log n} infinitely often.)

Next we prove (iii). First note that if there were only finitely many n with a_{n} = 0 then we would have s_{n} ≥ n − O(1), contradicting (v); hence (iii) is true for k = 0. Since a_{n} can increase by at most 1 at each step and there are infinitely many n with a_{n} = 0, to complete the proof of (iii) it suffices to show that (a_{n})_{n≥1} is unbounded.

To that end, for a given integer m ≥ 2 we apply the main result of Banks, Freiberg, and Turnage-Butterbaugh [3] to find a sequence of m + 1 consecutive primes with a large gap followed by a relatively dense cluster. Precisely, let k = k_{m+1} in the notation of [3], and set b_{j} = −m^{k+1−j} for j = 1, …, k. Then it is easy to see that the polynomial ∏_{j=1}^{k}(x + b_{j}) has no fixed prime divisor, so by [3, Theorem 1] there exists a subset {h_{0}, …, h_{m}} ⊆ {b_{1}, …, b_{k}} such that x + h_{0}, …, x + h_{m} are consecutive primes for infinitely many x ∈ ℤ.

Fix any such x, denote the corresponding primes by p_{0}, …, p_{m}, and write h_{i} = −m^{k+1−j_{i}}, where 1 ≤ j_{0} < ⋯ < j_{m} ≤ k. Then

(m − 1)(h_{m} − h_{1}) = (m − 1)(m^{k+1−j_{1}} − m^{k+1−j_{m}})
< m^{k+2−j_{1}} − m^{k+1−j_{1}} ≤ m^{k+1−j_{0}} − m^{k+1−j_{1}} = h_{1} − h_{0},

so that

p_{1} − p_{0} > (m − 1)(p_{m} − p_{1}) ≥ (m − 1)p_{m} − (p_{1} + p_{2} + ⋯ + p_{m−1}).

As in the proof of (v) above, we define sequences (s′_{n})_{n≥p_{1}}, (a′_{n})_{n>p_{1}}, and (d_{n})_{n≥p_{1}} by

s′_{p_{1}} = p_{1}, s′_{n+1} = s′_{n} + π(n + 1) − π(s′_{n}) for n ≥ p_{1},
a′_{n} = s′_{n} − s′_{n−1} for n > p_{1},

and

d_{n} = s′_{n} − s_{n} for n ≥ p_{1}.

As above we find that 0 ≤ d_{n+1} ≤ d_{n}, so

a′_{n} = a_{n} + d_{n} − d_{n−1} ≤ a_{n} for n > p_{1}.

A straightforward inductive argument now shows that

s′_{n} = p_{0}  for p_{0} ≤ n < p_{1},
s′_{n} = p_{0} + n − p_{1} + 1  for p_{1} ≤ n < p_{2},
s′_{n} = p_{0} + (p_{2} − p_{1}) + 2(n − p_{2} + 1)  for p_{2} ≤ n < p_{3},
⋮
s′_{n} = p_{0} + (p_{2} − p_{1}) + 2(p_{3} − p_{2}) + ⋯
+ (m − 2)(p_{m−1} − p_{m−2}) + (m − 1)(n − p_{m−1} + 1)  for p_{m−1} ≤ n < p_{m}.

In particular,

s′_{p_{m}−1} = p_{0} + (m − 1)p_{m} − (p_{1} + p_{2} + ⋯ + p_{m−1}) < p_{1},

so that

a_{p_{m}} ≥ a′_{p_{m}} = π(p_{m}) − π(s′_{p_{m}−1}) = m.

Since m was arbitrary, this completes the proof of (iii).

2 Some conjectures

It follows from (ii) and (iv) that

lim_{n→∞} \frac{a_{n}}{n} = 0 and lim_{n→∞} \frac{s_{n}}{n} = 1.  (8)

We further conjecture the following.

Conjecture 2.

(A) For any k ≥ 0, the set {n ≥ 1 : a_{n} = k} has a positive density δ_{k}, satisfying

δ_{1} > δ_{0} > δ_{2} > δ_{3} > δ_{4} > ⋯

(B) lim inf_{n→∞}(n − s_{n}) < ∞.

(C) For any integer b ≥ 2, the number A(b) = ∑_{n≥1} a_{n}b^{−n} ∈ ℝ is transcendental.

Part (A) of the conjecture is based on the numerical data shown in Table 2; note that the convergence is very slow, so it is difficult to measure the densities precisely, and in any case we do not expect them to be recognizable constants. In connection with (B), it seems likely from numerical computations that s_{n} = n − 2 infinitely often; by (iv) this would imply that lim inf_{n→∞}(n − s_{n}) = 2. If (a_{n})_{n≥1} were an automatic sequence then (C) would follow from the main result of Adamczewski, Bugeaud, and Luca [1].

k
i  0  1  2  3  4  5
1  4  5  1  0  0  0
2  21  65  14  0  0  0
3  219  577  195  9  0  0
4  2663  4990  2065  275  7  0
5  27671  48507  20265  3287  257  13
6  284408  475421  199765  36779  3443  181
7  2918543  4650175  1991476  395418  41464  2800
8  29607905  45960839  19809319  4108991  473258  37723
9  299530722  455176760  197289962  42282008  5235205  456865
10  3022594978  4517557589  1965289965  432413509  56484650  5291355
11  30450733004  44894741076  19590459294  4400511075  599692839  59396517
12  306392386246  446604857931  195374867235  44626996156  6295691446  652786704
13 3080065196771  4446030725007  1949223822125  451486351994  65543491929  7053078276
14 30940285500711 44287714979733 19452797930000 4559198048883 678055064108 75277782875
Table 2: Values of #{n ≤ 10^{i} : a_{n} = k} for 0 ≤ k ≤ 5 and 1 ≤ i ≤ 14.

In addition to the numerical evidence noted above, we provide the following theoretical evidence in support of the conjectures.

Theorem 3.

(i) #{n ≥ 1 : a_{n} = k} has positive upper density for at least one k ∈ {0, 1}.

(ii) We have #\{n ≤ x : a_{n} = 0\} ≫ \frac{x log log x}{log^{2} x} for all x ≥ 3 under the hypothesis that g(x) ≪ (log x)^{C} for some C > 1, and #\{n ≤ x : a_{n} = 0\} ≥ exp((log x)^{\frac{1}{4} −o(1)}) unconditionally.

(iii) lim inf_{n→∞} \frac{n−s_{n}}{log n} ≤ 1.

(iv) The number A(b) is irrational.

2.1 Proof of (i) and (ii)

We begin with an overview of the proof. First we show that if a_{n} has few zero terms then there must exist many long intervals I such that a_{n} = 1 for all n ∈ I. This immediately yields (i), and in turn implies that c := n−s_{n} is constant for n+1 ∈ I. In view of (4), for any n such that n, n + 1 ∈ I and n + 1 is prime, s_{n} must also be prime. Thus, the constellation of primes occurring in I is repeated on the shifted interval {n − c : n, n + 1 ∈ I}. Now the idea is to use results from the Selberg sieve (in particular [5, Lemma 5.1]) that bound the frequency of such coincidences of the constellations, and this results in a contradiction if a_{n} has too few zeros. There is a tradeoff between increasing the dimension of the sieve, which reduces the overall frequency asymptotically, and the combinatorial price paid for that increase. Optimizing the dimension then yields (ii).

Next we set some notation to be used in the proof. Let x > 0 be a large real number, and let r, T ∈ ℤ be parameters, to be specified in due course, satisfying

2 ≤ r ≤ T ≤ r(log x)^{\frac{r−1}{4r+2}} / log log x.

We regard r as fixed throughout the proof, so the meaning of ≪, O, o, “sufficiently large”, etc. may depend implicitly on r. Let K ≥ 1 be a large (absolute) constant, and define

H_{j} = Kj^{2}(log x)(log T) for 0 ≤ j ≤ T.

Next, set N = ⌊x⌋ and

N_{k} = #{1 ≤ n ≤ x : a_{n} = k} for k ≥ 0.

Then

N_{0} + N_{1} + N_{2} + ⋯ = N and N_{1} + 2N_{2} + ⋯ = s_{N},

so that

N_{0} − (N_{2} + 2N_{3} + ⋯) = N − s_{N} > 0.

Thus

N_{0} + (N_{2} + N_{3} + ⋯) ≤ N_{0} + (N_{2} + 2N_{3} + ⋯) < 2N_{0}.

This also shows that N_{1} + 2N_{0} > N, so that max\{N_{0}, N_{1}\} > \frac{1}{3}N. It follows that at least one of the sets \{n ≥ 1 : a_{n} = k\} for k ∈ \{0, 1\} has upper density ≥ \frac{1}{3}. This proves (i).

Next, setting N = {1 ≤ n ≤ x : a_{n} ≠ 1}, we have #N < 2N_{0}. Let

L = {ℓ ∈ ℤ : 1 ≤ ℓ ≤ x and a_{n} ≠ 1 for some n ∈ [ℓ − 1, ℓ + H_{T}] ∩ ℤ_{>0}}.

By [8, Corollary 2], the number of primes contained in L is at most

2π(H_{T} + 2)(#N + 1) ≤ 4π(H_{T} + 2)N_{0}.

Suppose, for the sake of contradiction, that 4π(H_{T} + 2)N_{0} ≤ \frac{1}{2}π(x). From now on we consider primes p ∈ [1, x] \ L, which is at least half of the primes p ≤ x. These primes have the property that a_{n} = 1 for all integers n satisfying p − 1 ≤ n ≤ p + H_{T}.

We need two easy facts about primes.

Lemma 4. Let p_{i} denote the ith prime. For a suitable choice of the constant K and all sufficiently large x, there are at most \frac{1}{4}π(x) primes p_{i} ≤ x for which there exists j ∈ \{1, …, T \} satisfying p_{i+j} − p_{i} > H_{j}.

Proof. Fix j ∈ {1, …, T }. Then, since j ≤ T = o(π(x)), we have

∑_{i=1}^{π(x)}(p_{i+j} − p_{i}) < ∑_{k=π(x)+1}^{π(x)+j} p_{k} = (1 + o(1))jx,

by the prime number theorem. Therefore, the number of i such that p_{i+j} − p_{i} > H_{j} is ≪ jx/H_{j} = x/(jH_{1}). Summing this over all j ≤ T, we get a bound of

≪ \frac{x}{H_{1}} ∑_{j≤T} \frac{1}{j} ≪ \frac{x log T}{H_{1}} ≪ \frac{π(x)}{K}.

For K sufficiently large this is less than \frac{1}{4}π(x).

Lemma 5. For a fixed choice of r ≥ 2, there are at most o(π(x)) primes p_{i} ≤ x satisfying the following conditions:

(i) p_{i+j} − p_{i} ≤ H_{j} for all j ∈ {0, …, T };

(ii) there are vectors (j_{1}, …, j_{r}), (j′_{1}, …, j′_{r}) ∈ ℤ^{r} such that

0 ≤ j_{1} < j_{2} < ⋯ < j_{r} ≤ T, 0 ≤ j′_{1} < j′_{2} < ⋯ < j′_{r} ≤ T,

and

p_{i+j_{1}} − p_{i+j′_{1}} = ⋯ = p_{i+j_{r}} − p_{i+j′_{r}} ≠ 0.

Proof. Let p_{i} be such a prime, and set

h_{j} = p_{i+j} − p_{i} for j ∈ {0, …, T }.

Let (j_{1}, …, j_{r}), (j′_{1}, …, j′_{r}) be as in (ii), and write

{j_{1}, …, j_{r}} ∪ {j′_{1}, …, j′_{r}} = {ℓ_{1}, …, ℓ_{k}},

with ℓ_{1} < ⋯ < ℓ_{k}. From our hypotheses it is clear that r + 1 ≤ k ≤ 2r. Let

d = h_{j_{1}} − h_{j′_{1}} = ⋯ = h_{j_{r}} − h_{j′_{r}}

denote the common difference. Swapping (j_{1}, …, j_{r}) and (j′_{1}, …, j′_{r}) if necessary, we may assume without loss of generality that d > 0, and it follows that j_{s} > j′_{s} for each s ∈ {1, …, r}.

For a fixed value of k, there are O(T^{k}) ways of choosing {j_{1}, …, j_{r}} and {j′_{1}, …, j′_{r}} of total cardinality k. If k = 2r then for each choice of indices, there are at most H_{T}^{r+1} choices for the pair of vectors v = (h_{j_{1}}, …, h_{j_{r}}), v′ = (h_{j′_{1}}, …, h_{j′_{r}}), since v′ is determined by v and d. If k < 2r then there are 2r − k pairs (s, t) such that j_{s} = j′_{t}; for each pair we have d = h_{j_{t}} − h_{j′_{t}} = h_{j_{t}} − h_{j_{s}}, so that h_{j_{t}} is determined by h_{j_{s}} and d. Hence, in general there are at most H_{T}^{k+1−r} choices for v, v′ for a given choice of indices. Thus, in total we find

≪ T^{k}H_{T}^{k+1−r} ≪ T^{3k+2−2r}((log T)(log x))^{k+1−r}

choices for v, v′ for our fixed k.

Let us first suppose that ℓ_{1} > 0. Then n = p_{i} is an integer such that the k + 1 distinct linear forms n, n + h_{ℓ_{1}}, …, n + h_{ℓ_{k}} are all prime. By [9, Ch. II, Satz 4.2], the number of such n ≤ x is

≪_{k} \frac{x}{(log x)^{k+1}} (\frac{E}{φ(E)})^{k} , where E = ∏_{1≤s≤k} h_{ℓ_{s}} · ∏_{1≤s<t≤k}(h_{ℓ_{t}} − h_{ℓ_{s}}).

Since h_{ℓ_{1}}, …, h_{ℓ_{k}} ≤ H_{T} ≪ log^{2} x, we have \frac{E}{φ(E)} ≪ log log log x. Hence, the number of possibilities for p_{i} is

≪ \frac{T^{3k+2−2r}(log T)^{k+1−r}x(log log log x)^{k}}{(log x)^{r}} ≤ \frac{T^{4r+2}(log T)^{r+1}x(log log log x)^{2r}}{(log x)^{r}}

≪ \frac{x(log log log x)^{2r}}{(log x)(log log x)^{3r+1}} = o(π(x)).

If ℓ_{1} = 0 then we lose one linear form, but gain from the fact that j′_{1} and h_{j′_{1}} are fixed at 0. This effectively replaces k by k − 1 in the above analysis, so we again find o(π(x)) possibilities for p_{i}. Finally, summing over k ∈ {r + 1, …, 2r} concludes the proof of the lemma.

The following is Lemma 5.1 of Ford, Konyagin, and Luca [5].

Lemma 6. There is a positive constant δ so that the following holds. Let a_{1}, …, a_{k} be positive integers, let b_{1}, …, b_{k} be integers and let ξ(p) be the number of solutions of

∏_{i=1}^{k}(a_{i}n + b_{i}) ≡ 0 (mod p).

If x ≥ 10, 1 ≤ k ≤ δ \frac{log x}{log log x}, and

B := ∑_{p} (\frac{k − ξ(p)}{p}) log p ≤ δ log x,

then the number of integers n ≤ x for which a_{1}n + b_{1}, …, a_{k}n + b_{k} are all prime and > k is

≪ \frac{2^{k}k!𝔖x}{(log x)^{k}} exp(O(\frac{kB + k^{2} log log x}{log x})) , where 𝔖 = ∏_{p} (1 − \frac{ξ(p)}{p}) (1 − \frac{1}{p})^{−k} . (9)

We are now ready to go. As we said, we work with primes p_{i} ≤ x that are not in L. The number of them is at least \frac{1}{2}π(x). We discard all p_{i} such that p_{i+j} − p_{i} > H_{j} holds for some j = 1, …, T. By Lemma 4, there are at most \frac{1}{4}π(x) such primes. Next, applying Lemma 5, by removing a further o(π(x)) values of p_{i}, we may assume that as j and j′ range over {0, …, T }, each non-zero difference p_{i+j} − p_{i+j′} occurs with multiplicity at most r − 1. After this we are left with at least (\frac{1}{4} − o(1))π(x) primes p_{i}.

Set c = p_{i} − s_{p_{i}}. By Theorem 1(iv) and the definition of N_{0}, we have

0 < c ≤ M := min{g(x), N_{0}}.

Now consider p_{i}, p_{i+1}, …, p_{i+T}. These are of the form p_{i+j} = p_{i} + h_{j} for some h_{j} ≤ H_{j}, as in the proof of Lemma 5. On the other hand, p_{i+T} − p_{i} ≤ H_{T}, and since a_{n} = 1 for p_{i} − 1 ≤ n ≤ p_{i} + H_{T}, we have s_{n} = n − c for p_{i} − 2 ≤ n ≤ p_{i+T}. Applying (4) with n = p_{i+j} − 1, we have

0 = a_{p_{i+j}} − a_{p_{i+j}−1} = (π(p_{i+j}) − π(p_{i+j} − 1)) − (π(s_{p_{i+j}−1}) − π(s_{p_{i+j}−2}))
= 1 − (π(p_{i+j} − 1 − c) − π(p_{i+j} − 2 − c)).

Hence, p_{i+j} − 1 − c = p_{i} + h_{j} − c − 1 is prime.

Therefore, n = p_{i} is such that n + h_{j} and n + h_{j} − c − 1 are all primes for j = 0, …, T. This is 2T + 2 linear forms, but they might not all be distinct. Let m be the cardinality of the intersection

{h_{j} : 0 ≤ j ≤ T } ∩ {h_{j} − c − 1 : 0 ≤ j ≤ T }.

Then there exist j_{0} < j_{1} < ⋯ < j_{m} and j′_{0} < j′_{1} < ⋯ < j′_{m} with

h_{j_{1}} − h_{j′_{1}} = ⋯ = h_{j_{m}} − h_{j′_{m}} = c + 1,

so that

p_{i+j_{1}} − p_{i+j′_{1}} = ⋯ = p_{i+j_{m}} − p_{i+j′_{m}} > 0.

By our construction, we must have m < r; in particular, there are at least 2T +3−r distinct forms among the n + h_{j} and n + h_{j} − c − 1 for j = 0, …, T. Hence we may apply Lemma 6 for some k ∈ [2T + 3 − r, 2T + 2] ∩ ℤ.

We need to check the hypothesis on B and estimate some of the parameters in (9). For B, we partition the primes into S_{1} ∪ S_{2} ∪ S_{3}, where

S_{1} = {p : p ≤ log^{2} x or p | (c + 1)}, S_{2} = {p : ξ(p) < k} \ S_{1}, S_{3} = {p : ξ(p) = k} \ S_{1}.

Since c ≤ x, c + 1 has O(log x/ log log x) prime factors exceeding log^{2} x. Hence,

∑_{p∈S_{1}} (\frac{k − ξ(p)}{p}) log p ≤ k ∑_{p≤log^{2} x} \frac{log p}{p} + k ∑_{\begin{matrix}p|(c+1) \\ p>log^{2} x \end{matrix}} \frac{log p}{p}

≪ T log log x + \frac{T}{log x} ≪ T log log x.

For any prime p ∈ S_{2}, there is a double solution n modulo p to

∏_{0≤j≤T}(n + h_{j}) · ∏_{\begin{matrix}0≤j≤T \\ h_{j}−c−1∉\{h_{0},...,h_{T} \} \end{matrix}}(n + h_{j} − c − 1) ≡ 0 (mod p).

If the double root comes from the forms n + h_{j} for j = 0, …, T, we get that p divides h_{j_{2}} − h_{j_{1}} for some j_{1}, j_{2} with 0 ≤ j_{1} < j_{2} ≤ T. But this is impossible since p > log^{2} x and h_{j} ≤ H_{T} < log^{2} x for large x. The same argument shows that the double solution cannot come from two factors of the form n + h_{j} − c − 1 for j ∈ {0, …, T }. So any double root must appear once from the first set of forms and once from the second, so that p divides c + 1 + h_{j′} − h_{j} ≠ 0 for some j, j′ ∈ {0, …, T }. These numbers all lie in the interval [c + 1 − H_{T} , c + 1 + H_{T}], and since c ≤ x, each has O(log x/ log log x) prime factors exceeding log^{2} x. Thus,

#S_{2} ≪ \frac{H_{T} log x}{log log x} ≪ log^{3} x.

Moreover, writing m = k − ξ(p), there exist j_{1} < ⋯ < j_{m}, j′_{1} < ⋯ < j′_{m} such that

h_{j_{1}} − h_{j′_{1}} ≡ ⋯ ≡ h_{j_{m}} − h_{j′_{m}} ≡ c + 1 (mod p).

Since p ∤ (c + 1) and 2H_{T} + 1 < log^{2} x for large x, this implies that

h_{j_{1}} − h_{j′_{1}} = ⋯ = h_{j_{m}} − h_{j′_{m}} ≠ 0.

Thus we have m < r, so that ξ(p) ≥ k + 1 − r. Therefore

∑_{p∈S_{2}} (\frac{k − ξ(p)}{p}) log p ≤ (r − 1) ∑_{log^{2} x<p≤O(log^{3} x)} \frac{log p}{p} ≪ log log x.

Finally, the primes in S_{3} do not contribute to B. Thus, the bound on B holds, and in fact B = O(T log log x).

We now estimate (9). Since B = O(T log log x), the factor involving exp tends to 1 as x → ∞, so it is smaller than 2 for large x. In the expression for 𝔖, the primes p ∈ S_{1} contribute at most

(\frac{c + 1}{φ(c + 1)})^{k} ∏_{p≤log^{2} x} (1 − \frac{1}{p})^{−k} = O(log log x)^{k} exp(k ∑_{p≤log^{2} x} \frac{O(1)}{p})

= exp(O(T log log log x)).

The contribution from p ∈ S_{2} is at most

∏_{p∈S_{2}} (1 − \frac{k + 1 − r}{p}) (1 − \frac{1}{p})^{−k} = ∏_{p∈S_{2}} (1 − \frac{k + 1 − r}{p}) (1 + \frac{k}{p} + O(\frac{k^{2}}{p^{2}} ))

= ∏_{p∈S_{2}} (1 + O(\frac{1}{p})) = exp(∑_{p∈S_{2}} \frac{O(1)}{p}) = e^{O(1)}.

Similarly, from p ∈ S_{3} we get a contribution of

∏_{p∈S_{3}} (1 − \frac{k}{p}) (1 − \frac{1}{p})^{k} = exp(k ∑_{p>log^{2} x} \frac{O(1)}{p^{2}}) = exp(O(\frac{k}{log x})) = e^{O(1)}.

Thus, in total we have

𝔖 = exp(O(T log log log x)).

Applying Lemma 6, the number of n ≤ x of this form is

≪ \frac{2^{k}k!x}{(log x)^{k}} exp(O(T log log log x)).

Since 2k ≤ 4T + 4 < log x for large x, this is largest when k = 2T + 3 − r. Using also that

2^{2T +3−r}(2T + 3 − r)! = T^{2T +8−4r}e^{O(r log T)+O(T)} = T^{2T +8−4r}e^{O(T)},

we obtain

≪ \frac{T^{2T +8−4r}π(x)}{(log x)^{2T +2−r}} exp(O(T log log log x)).

This is for fixed c, h_{1}, …, h_{T}. The number of choices for these parameters is at most

MH_{1} ⋯ H_{T} = M(T!)^{2}H_{1}^{T} ≤ MT^{2T} (log x)^{T} exp(O(T log log log x)).

Thus, in total the number of possibilities is

≪ \frac{Mπ(x)}{exp((T + 2 − r) log(\frac{log x}{T^{4}}))} exp(O(T log log log x)).

This must account for at least (\frac{1}{4} − o(1))π(x) primes, so for sufficiently large x we have

M = min\{g(x), N_{0}\} ≫ exp((T + 2 − r) log(\frac{log x}{T^{4}}) − O(T log log log x)) .

If g(x) ≪ (log x)^{C} for some C > 1, then taking r = 2 and T = ⌊C⌋ + 1 results in a contradiction for sufficiently large x. Hence, our hypothesis that 4π(H_{T} + 2)N_{0} ≤ \frac{1}{2}π(x) must be false, and it follows that N_{0} ≫ x(log log x)/ log^{2} x.

On the other hand, assuming that N_{0} ≪ x/ log^{2} x (and making no hypothesis on g(x)), we can take T = ⌊r(log x)^{\frac{r−1}{4r+2}} / log log x⌋, and we conclude that N_{0} ≥ exp((log x)^{\frac{r−1}{4r+2}} ) for all sufficiently large x. Since this is true for every r ≥ 2, we have N_{0} ≥ exp((log x)^{\frac{1}{4} −o(1)}).

2.2 Proof of (iii)

Consider positive integers M < N, and let h = min{n − s_{n} : M ≤ n < N}. Then

s_{N} − s_{M} = ∑_{n=M}^{N−1} a_{n+1} = ∑_{n=M}^{N−1}(π(n + 1) − π(s_{n})) ≥ ∑_{n=M}^{N−1}(π(n + 1) − π(n − h))

= ∑_{i=0}^{h}(π(N − i) − π(M − i)) ≥ (h + 1)(π(N − h) − π(M)).

By Theorem 1(iv) and the result of Baker, Harman, and Pintz [2], we have

h ≤ g(M) ≤ M^{21/40} for sufficiently large M.

Choosing N = ⌈M + M^{7/12}⌉ and applying Heath-Brown’s asymptotic [7] for primes in short intervals, we have

π(N − h) − π(M) = (1 + o(1))\frac{N − M}{log M} as M → ∞.

On the other hand,

s_{N} − s_{M} ≤ N − (M − g(M)) ≤ (1 + o(1))(N − M),

so that h ≤ (1 + o(1)) log M. Thus, every sufficiently large interval [M, M + M^{7/12}) contains an integer n with n − s_{n} ≤ (1 + o(1)) log n.

2.3 Proof of (iv)

Let N be a large natural number, and write {1, …, N} as a disjoint union I_{1} ∪ ⋯ ∪ I_{J} of intervals I_{j} such that a_{n} is constant on each I_{j} and J is as small as possible. Setting m_{j} = max I_{j} for j ≤ J, we have either m_{j} = N or a_{m_{j}+1} ≠ a_{m_{j}}. From (4) we see that if a_{n+1} ≠ a_{n} then either π(n + 1) ≠ π(n) or π(s_{n}) ≠ π(s_{n−1}). Since both sequences π(n) and π(s_{n−1}) are non-decreasing and s_{n} ≤ n for all n, it follows that

J ≤ 1 + #{n < N : a_{n+1} ≠ a_{n}} ≤ 1 + 2π(N).

Thus, for at least one of the intervals, say I_{j} = {n_{1}, …, n_{2}}, we have

#I_{j} = n_{2} − n_{1} + 1 ≥ \frac{N}{1 + 2π(N)}.

By the prime number theorem, for any fixed ε > 0 this exceeds (\frac{1}{2} −ε) log N for all sufficiently large N.

Suppose A(b) = u/v is rational. Then, multiplying by v(b − 1)b^{n_{1}−1}, we obtain

u(b − 1)b^{n_{1}−1} = v(b − 1)b^{n_{1}−1} ∑_{n=1}^{∞} \frac{a_{n}}{b^{n}} .

Let c = a_{n_{1}}. Since a_{n} is constant for n_{1} ≤ n ≤ n_{2}, we have

u(b − 1)b^{n_{1}−1} = v(b − 1) ∑_{n=1}^{n_{1}−1} a_{n}b^{n_{1}−1−n} + v(b − 1)c ∑_{n=n_{1}}^{n_{2}} b^{n_{1}−1−n} + v(b − 1) ∑_{n≥n_{2}+1} a_{n}b^{n_{1}−1−n}

= v(b − 1) ∑_{n=1}^{n_{1}−1} a_{n}b^{n_{1}−1−n} + vc(1 − b^{n_{1}−n_{2}−1}) + v(b − 1)b^{n_{1}−n_{2}−1} ∑_{m≥1} \frac{a_{n_{2}+m}}{b^{m}} .

Hence,

vb^{n_{1}−n_{2}−1} ((b − 1) ∑_{m≥1} \frac{a_{n_{2}+m}}{b^{m}} − c) = u(b − 1)b^{n_{1}−1} − v(b − 1) ∑_{n=1}^{n_{1}−1} a_{n}b^{n_{1}−1−n} − vc (10)

is an integer.

On the other hand, since 0 ≤ a_{n_{2}+m} ≤ c + m for m ≥ 1, we have

−c ≤ (b − 1) ∑_{m≥1} \frac{a_{n_{2}+m}}{b^{m}} − c ≤ (b − 1) ∑_{m≥1} \frac{c + m}{b^{m}} − c = \frac{b}{b − 1}.

Hence the left-hand side of (10) is bounded in modulus by

\frac{(c + 2)v}{b^{n_{2}−n_{1}+1}} ≤ \frac{(c + 2)v}{N^{( \frac{1}{2} −ε) log b}} ≪ \frac{v\sqrt{g(N)}}{N^{( \frac{1}{2} −ε) log b}} .

From Baker, Harman, and Pintz [2], we have g(N) ≤ N^{21/40} for sufficiently large N. Since log b ≥ log 2 > \frac{21}{40}, for small enough ε this expression tends to 0 as N → ∞. Since it has to be an integer, it must be 0 for all sufficiently large N.

Therefore,

∑_{m≥1} \frac{a_{n_{2}+m}}{b^{m}} = \frac{c}{b − 1} = ∑_{m≥1} \frac{c}{b^{m}} .

By Theorem 1(iii) there exists n_{3} > n_{2} such that a_{n_{3}} = 0. Thus, we have

∑_{j=1}^{∞} \frac{a_{n_{3}+j}}{b^{n_{3}+j}} = ∑_{m≥1} \frac{c}{b^{m}} − ∑_{m=1}^{n_{3}−n_{2}−1} \frac{a_{n_{2}+m}}{b^{m}} = ∑_{m=1}^{n_{3}−n_{2}−1} \frac{c − a_{n_{2}+m}}{b^{m}} + \frac{cb^{n_{2}−n_{3}+1}}{b − 1} .

Multiplying both sides by (b − 1)b^{n_{3}−1}, we see that the right-hand side is an integer, so

(b − 1) ∑_{j≥1} \frac{a_{n_{3}+j}}{b^{j+1}} ∈ ℤ.

On the other hand, we have 0 ≤ a_{n_{3}+j} ≤ j, and by Theorem 1(iii) both inequalities are strict for infinitely many j. Hence,

0 < (b − 1) ∑_{j≥1} \frac{a_{n_{3}+j}}{b^{j+1}} < (b − 1) ∑_{j≥1} \frac{j}{b^{j+1}} = 1.

This is a contradiction, so A(b) must be irrational.

3 Generalizations and suggestions for further work

The sequence a_{n} admits a vast generalization via sequences of the form

a_{f}(n) = π(f(n)) − π(∑_{k=1}^{n−1} a_{f}(k))

for various functions f. For instance, choosing f(n) = tn for a fixed integer t > 0, our proof of (8) can be generalized to show that

lim_{n→∞} \frac{a_{f}(n)}{n} = 0 and lim_{n→∞} \frac{s_{f}(n)}{n} = t,

where s_{f}(n) = ∑_{k=1}^{n} a_{f}(k) denotes the summatory function. One can pose many of the same questions and conjectures for these sequences.

Another possible generalization is to consider the same recurrence formula with different initial conditions. However, it turns out that this offers no increase in generality, in the sense that if (a′_{n})_{n≥1} is any sequence satisfying

a′_{n} = π(n) − π(∑_{k=1}^{n−1} a′_{k}) for n > n_{0}

for some n_{0} ≥ 0, then a′_{n} = a_{n} for all sufficiently large n. (The same proof shows that taking f(n) = n + c for some c ∈ ℤ in the above, we have a_{f}(n) = a_{n+c} for sufficiently large n.) To see this, let s′_{n} be the summatory sequence of a′_{n}, and set d_{n} = s′_{n} − s_{n}. Then, as in the proof of Theorem 1(v), we find that |d_{n+1}| ≤ |d_{n}|. From that proof we also see that each of the sequences (s_{n})_{n≥1} and (s_{n} + 1)_{n≥1} assumes infinitely many prime values, and it follows that d_{n} eventually reaches 0. Thus s′_{n} = s_{n} and a′_{n} = a_{n} for sufficiently large n.

At the same time, there are several possible avenues for further research on (a_{n}). We conclude with a few speculative suggestions.

1. Assuming Cramér’s conjecture, by Theorem 1(ii) we have

#\{n ≤ x : a_{n} ≠ 0\} ≥ \frac{∑_{n≤x} a_{n}}{max_{n≤x} a_{n}} ≫ \frac{x\sqrt{log log x}}{log x}.

This could be improved with some information on higher moment statistics of a_{n}. For instance, can one give a non-trivial upper bound for ∑_{n≤x} a_{n}^{2}?

2. It is easy to see that the difference sequence a_{n+1}−a_{n} is almost always 0, so a_{n} has many long constant runs. (This idea was used in the proof of Theorem 3(iv).) Assuming either Conjecture 2(A) or Dickson’s conjecture, one can see that for any k ≥ 0 there are arbitrarily long runs of n with a_{n} = k. Unconditionally, by Theorem 3(i) this holds for at least one k ∈ {0, 1}, and from the proof of Theorem 1(iii) we get arbitrarily long runs on which a_{n} is both constant and arbitrarily large. Can one give an unconditional proof of long constant runs for a specific value of k?

3. The previous question admits many generalizations. For instance, assuming Dickson’s conjecture, one can see that there are arbitrarily long arithmetic progressions n, n + d, …, n + kd such that a_{n+jd} = j for j = 0, …, k. Can this be proved unconditionally?

4 Acknowledgments

Altug Alkan would like to thank Robert Israel, Remy Sigrist and Giovanni Resta for their valuable computational assistance regarding OEIS contributions \underline{A335294} and \underline{A335337}.

References

[1] B. Adamczewski, Y. Bugeaud, and F. Luca, Sur la complexité des nombres algébriques, C. R. Math. Acad. Sci. Paris 339 (2004), 11–14.

[2] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. 83 (2001), 532–562.

[3] W. D. Banks, T. Freiberg, and C. L. Turnage-Butterbaugh, Consecutive primes in tuples, Acta Arith. 167 (2015), 261–266.

[4] K. Ford, B. Green, S. Konyagin, J. Maynard, and T. Tao, Long gaps between primes, J. Amer. Math. Soc. 31 (2018), 65–105.

[5] K. Ford, S. V. Konyagin, and F. Luca, Prime chains and Pratt trees, Geom. Funct. Anal. 20 (2010), 1231–1258.

[6] D. M. Gordon and G. Rodemich, Dense admissible sets. In Algorithmic number theory (Portland, OR, 1998), Vol. 1423 of Lecture Notes in Comput. Sci., pp. 216–225. Springer, 1998.

[7] D. R. Heath-Brown, The number of primes in a short interval, J. Reine Angew. Math. 389 (1988), 22–63.

[8] H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134.

[9] K. Prachar, Primzahlverteilung, Springer-Verlag, 1957.

2020 Mathematics Subject Classification: Primary 11A41; Secondary 11B83. Keywords: prime-counting function.

(Concerned with sequences \underline{A335294} and \underline{A335337}.)

Received June 12 2020; revised version received January 27 2021. Published in Journal of Integer Sequences, January 31 2021.

Return to Journal of Integer Sequences home page.