Erdős #1204 · number theory

Erdős [Er80] attributes this problem to Elliott. The bounds are misstated in [Er80], but it is known that

The upper bound Erdős attributes to Davenport, and follows simply by taking the $k$ smallest primes $>k$. The lower order terms have been improved by Hensley and Richard [HeRi73] (see Section 10 of [Po14c] for more details).

The lower bound is originally due to Elliott [El65], but was rediscovered by the Polymath project on bounded gaps between primes (see [Po14c]).

An upper bound of $\pi(x+y)\leq \pi(x)+(1+o(1))\pi(y)$ (see [855]) together with the prime tuples conjecture would imply $A(k)\geq (1+o(1))k\log k$.

It is trivial that $B(k)<A(k)$. Taking the first $k$ primes which are $>k$ implies

and since $a_j\geq A(j)$ we have $B(k) \geq \frac{1}{k}\sum_{1\leq j\leq k}A(j)$, whence if $A(k)\geq (c-o(1))k\log k$ we have $B(k) \geq (c/2-o(1))k\log k$, and so it is likely that

In [Er80] Erdős also asks about the behaviour of $a_k$ where $a_1<a_2<\cdots$ is the greedy admissible sequence (i.e. $a_1=0$ and $a_{i+1}$ is the smallest integer $>a_{i-1}$ such that $a_1,\ldots,a_i$ is admissible).

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.