The peculiar quantitative form of Erdős' question was motivated by an old result of Rankin [Ra38], who proved there exists some constant $C>0$ such that the claim holds. Solved by Maynard [Ma16] and Ford, Green, Konyagin, and Tao [FGKT16]. The best bound available, due to all five authors [FGKMT18], is that there are infinitely many $n$ such that \[p_{n+1}-p_n\gg \frac{\log\log n\log\log\log\log n}{\log\log \log n}\log n.\] The likely truth is a lower bound like $\gg(\log n)^2$. In [Er97c] Erdős revised the value of this problem to \$5000 and reserved the \$10000 for a lower bound of $>(\log n)^{1+c}$ for some $c>0$.

See also [687].

Let $S$ be the set of limit points of $(p_{n+1}-p_n)/\log n$. This problem asks whether $S=[0,\infty]$. Although this conjecture remains unproven, a lot is known about $S$. Some highlights:

• $\infty\in S$ by Westzynthius' result [We31] on large prime gaps,
• $0\in S$ by the work of Goldston, Pintz, and Yildirim [GPY09] on small prime gaps,
• Erdős [Er55] and Ricci [Ri56] independently showed that $S$ has positive Lebesgue measure,
• Hildebrand and Maier [HiMa88] showed that $S$ contains arbitrarily large (finite) numbers,
• Pintz [Pi16] showed that there exists some small constant $c>0$ such that $[0,c]\subset S$,
• Banks, Freiberg, and Maynard [BFM16] showed that at least $12.5\%$ of $[0,\infty)$ belongs to $S$,
• Merikoski [Me20] showed that at least $1/3$ of $[0,\infty)$ belongs to $S$, and that $S$ has bounded gaps.

In [Er85c] and [Er97c] Erdős asks whether $S$ is everywhere dense.

Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'. (In [Er85c] he goes further and offers 'all the money I can earn, beg, borrow or steal for [a disproof]'.)

Indeed, the answer is yes, as proved by Banks, Freiberg, and Turnage-Butterbaugh [BFT15] with an application of the Maynard-Tao machinery concerning bounded gaps between primes [Ma15]. They in fact prove that, for any $m\geq 1$, there are infinitely many $n$ such that \[d_n<d_{n+1}<\cdots <d_{n+m}\] and infinitely many $n$ such that \[d_n> d_{n+1}>\cdots >d_{n+m}.\]

Crocker [Cr71] has proved there are are $\gg\log\log N$ such integers in $\{1,\ldots,N\}$. Pan [Pa11] improved this to $\gg_\epsilon N^{1-\epsilon}$ for any $\epsilon>0$. Erdős believed this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.

The sequence of such numbers is A006286 in the OEIS.

See also [10], [11], and [16].

Erdős described this as 'probably unattackable'. In [ErGr80] Erdős and Graham suggest that no such $k$ exists. Gallagher [Ga75] has shown that for any $\epsilon>0$ there exists $k(\epsilon)$ such that the set of integers which are the sum of a prime and at most $k(\epsilon)$ many powers of 2 has lower density at least $1-\epsilon$.

Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of 2 suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers. (The restriction to odd integers is important here - for example, Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ (see [9]) suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).

See also [9], [11], and [16].

Erdős suggested that a computer could be used to explore this, and did not see any other method to attack this.

Tao [Ta23] has proved that this series does converge assuming a strong form of the Hardy-Littlewood prime tuples conjecture.

In [Er98] Erdős further conjectures that \[\sum_{n=1}^\infty (-1)^n \frac{1}{n(p_{n+1}-p_n)}\] converges and \[\sum_{n=1}^\infty (-1)^n \frac{1}{p_{n+1}-p_n}\] diverges. He further conjectures that \[\sum_{n=1}^\infty (-1)^n \frac{1}{n(p_{n+1}-p_n)(\log\log n)^c}\] converges for every $c>0$, and reports that he and Nathanson can prove this for $c>2$ (and conditionally for $c=2$).

Erdős called this conjecture 'rather silly'. Using covering congruences Erdős [Er50] proved that the set of such odd integers contains an infinite arithmetic progression.

Chen [Ch23] has proved the answer is no.

See also [9], [10], and [11].

The first prime without this property is $97$. The sequence of such primes is A038133 in the OEIS. These are called cluster primes.

Blecksmith, Erdős, and Selfridge [BES99] proved that the number of such primes is \[\ll_A \frac{x}{(\log x)^A}\] for every $A>0$, and Elsholtz [El03] improved this to \[\ll x\exp(-c(\log\log x)^2)\] for every $c<1/8$.

Erdős remarks that the last conjecture is probably easy, and that similar questions can be asked about $\sigma(n)$.

Solved by Tao [Ta23b], who proved that \[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]

In [Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.

Green and Tao [GrTa08] have proved that there must always exist some $k$ primes in arithmetic progression, but these need not be consecutive. Erdős called this conjecture 'completely hopeless at present'.

The existence of such progressions for small $k$ has been verified for $k\leq 10$, see the Wikipedia page. It is open, even for $k=3$, whether there are infinitely many such progressions.

See also [219].

It follows from the prime number theorem that such a progression has length $\leq(1+o(1))\log N$.

There are odd integers $m$ such that none of $2^km+1$ are prime, which arise from covering systems (i.e. one shows that there exists some $n$ such that $(2^km+1,n)>1$ for all $k\geq 1$). Erdős and Graham also ask whether there is such an $m$ where a covering system is not 'responsible'. The answer is probably no since otherwise this would imply there are infinitely many Fermat primes of the form $2^{2^t}+1$.

In [Er85c] Erdős also conjectures that $d_n=d_{n+1}=\cdots=d_{n+k}$ is solvable for every $k$.

The answer is yes, proved by Green and Tao [GrTa08]. The stronger claim that there are arbitrarily long arithmetic progressions of consecutive primes is still open.

See also [3] and [141].

Cramer proved an upper bound of $O(N(\log N)^4)$ conditional on the Riemann hypothesis. The prime number theorem immediately implies a lower bound of $\gg N(\log N)^2$.

The values of the sum are listed at A074741 on the OEIS.

Erdős [Er50] proved that there are infinitely many $n$ such that $f(n)\gg \log\log n$. Erdős could not even prove that there do not exist infinitely many integers $n$ such that for all $1< 2^k<n$ the number $n-2^k$ is prime (probably $n=105$ is the largest such integer).

The sequence of values of $f(n)$ is A109925 on the OEIS.

See also [237].

Erdős [Er50] proved this when $A=\{2^k : k\geq 0\}$. Solved by Chen and Ding [ChDi22].

See also [236].

This is well-known if $c_1$ is sufficiently small.

Originally asked to Erdős by Wintner.

The limit is infinite for a finite set of primes, which follows from a theorem of Pólya [Po18], that if $P(n)$ is a quadratic integer polynomial without repeated roots then as $n\to \infty$ the largest prime factor of $f(n)$ also approaches infinity. Indeed, if $P$ is a finite set of primes and $(a_i)$ is the set of integers divisible only by primes in $P$, and $a_{i+1}-a_i$ is bounded, then there exists some $k$ such that $a_{i+1}=a_i+k$ infinitely often, which contradicts Pólya's theorem with $f(n)=n(n+k)$.

Tijdeman [Ti73] proved that, if $P$ is a finite set of primes, then \[a_{i+1}-a_i \gg \frac{a_i}{(\log a_i)^C}\] for some constant $C>0$ depending on $P$.

Tijdeman [Ti73] resolved this question, proving that, for any $\epsilon>0$, there exists an infinite set of primes $P$ such that, with $a_i$ defined as above, \[a_{i+1}-a_i \gg a_i^{1-\epsilon}.\]

See also [368].

Originally asked to Erdős by Kalmár. Erdős believed the answer is yes. Romanoff [Ro34] proved that the answer is yes if $C$ is an integer.

Even the case $k=3$ seems difficult. This may be true with the primes replaced by any set $A\subseteq \mathbb{N}$ such that \[\lvert A\cap [1,N]\rvert \gg N/\log N\] and \[\sum_{\substack{n\in A\\ n\leq N}}\frac{1}{n} -\log\log N\to \infty\] as $N\to \infty$.

For $k=1$ or $k=2$ any set $A$ such that $\sum_{n\in A}\frac{1}{n}=\infty$ has this property.

Erdős and Moser [Mo63] considered the case when $A$ is the set of primes, and conjectured that the $\limsup$ of the number of such representations in this case is infinite. They could not even prove that the upper density of the set of integers representable in this form is positive.

Cedric Pilatte has observed that a positive solution to this follows from a result of Shiu [Sh00]: for any $k\geq 1$ and $(a,q)=1$ there exist infinitely many $k$-tuples of consecutive primes $p_m,\ldots,p_{m+{k-1}}$ all of which are congruent to $a$ modulo $q$.

Indeed, we apply this with $k=q=d$ and $a=1$ and let $p_m,\ldots,p_{m+{d-1}}$ be consecutive primes all congruent to $1$ modulo $d$, with $m>n+1$. If $p_{n+1}+\cdots+p_{m-1}\equiv r\pmod{d}$ with $1\leq r\leq d$ then \[d \mid p_{n+1}+\cdots +p_m+\cdots+p_{m+d+r-1}.\]

Erdős and Graham could show this is true (assuming the prime $k$-tuple conjecture) if we replace $\liminf$ by $\limsup$.

A problem of Ostmann, sometimes known as the 'inverse Goldbach problem'. The answer is surely no. The best result in this direction is due to Elsholtz and Harper [ElHa15], who showed that if $A,B$ are such sets then for all large $x$ we must have \[\frac{x^{1/2}}{\log x\log\log x} \ll \lvert A \cap [1,x]\rvert \ll x^{1/2}\log\log x\] and similarly for $B$.

Elsholtz [El01] has proved there are no infinite sets $A,B,C$ such that $A+B+C$ agrees with the set of prime numbers up to finitely many exceptions.

See also [432].

Pomerance [Po79] has proved the $\limsup$ is at least $2$.

Erdős and Graham write this is 'almost certainly' true, but the proof is beyond our ability, for two reasons (at least):

• Firstly, one has to rule out the possibility of many primes $q$ such that $p_k<q^2<p_{k+1}$. There should be at most one such $q$, which would follow from $p_{k+1}-p_k<p_k^{1/2}$, which is essentially the notorious Legendre's conjecture.
• The small primes also cause trouble.

Erdős and Graham report they can show \[f(n,t) \gg \frac{t}{\log t}.\]

This follows from 'plausible assumptions on the distribution of primes' (as does the question with $k^2$ replaced by $k^d$ for any $d$); the challenge is to prove this unconditionally.

Erdős observed that Cramer's conjecture \[\limsup_{k\to \infty} \frac{p_{k+1}-p_k}{(\log k)^2}=1\] implies that for all $\epsilon>0$ and all sufficiently large $n$ there exists some $k$ such that \[p(n+k)>e^{(1-\epsilon)\sqrt{k}}.\] There is now evidence, however, that Cramer's conjecture is false; a more refined heuristic by Granville [Gr95] suggests this $\limsup$ is $2e^{-\gamma}\approx 1.119\cdots$, and so perhaps the $1+\epsilon$ in the second question should be replaced by $2e^{-\gamma}+\epsilon$.

See also [681] and [682].

Related to questions of Erdős, Eggleton, and Selfridge. This may be true with $k^2$ replaced by $k^d$ for any $d$.

See also [680] and [682].

Erdős first thought this should be true for all large $n$, but found a (conditional) counterexample: Dickson's conjecture says there are infinitely many $d$ such that \[2183+30030d\textrm{ and }2201+30030d\] are both prime, and then they must necessarily be consecutive primes. These give a counterexample since $30030=2\cdot 3 \cdot 5\cdot 7\cdot 11\cdot 13$ and every integer in $[2184,2200]$ is divisible by at least one of these primes.

See also [680] and [681].

A theorem of Sylvester and Schur states that this is $>k$ if $k\leq n/2$. Erdős writes it 'seems certain' that this holds for every $c>0$, with only a finite number of exceptions (depending on $c$). Standard heuristics on prime gaps suggest that the largest prime divisor of $\binom{n}{k}$ is in fact \[> \min(n-k+1, e^{c\sqrt{k}})\] for some constant $c>0$.

A classical theorem of Mahler states that for any $\epsilon>0$ and integers $k$ and $l$ then, writing \[(n+1)\cdots (n+k) = ab\] where the only primes dividing $a$ are $\leq l$ and the only primes dividing $b$ are $>l$, we have $a < n^{1+\epsilon}$ for all sufficiently large (depending on $\epsilon,k,l$) $n$.

Mahler's theorem implies $f(n)\to \infty$ as $n\to \infty$, but is ineffective, and so gives no bounds on the growth of $f(n)$.

One can similarly ask for estimates on the smallest integer $f(n,k)$ such that if $m$ is the factor of $\binom{n}{k}$ containing all primes $\leq f(n,k)$ then $m > n^2$.

It is trivial that the number of prime factors is \[>\frac{\log \binom{n}{k}}{\log n},\] and this inequality becomes (asymptotic) equality if $k>n^{1-o(1)}$.

A problem of Deaconescu. Erdős expects that the least such prime is much smaller than $P$, and in fact satisfies $p\leq n^{O(1)}$. Deaconescu has verified this conjecture for $n\leq 1000$.

For just $x,y$ and $x+1,y+1$ one can take \[x=2(2^r-1)\] and \[y = x(x+2).\] Erdős also asked whether there are any other examples. Matthew Bolan has observed that $x=75$ and $y=1215$ is another example, since \[75 = 3\cdot 5^2 \textrm{ and }1215 = 3^5\cdot 5\] while \[76 = 2^2\cdot 19\textrm{ and }1216 = 2^6\cdot 19.\] No other exampes are known. This sequence is listed as A343101 at the OEIS.

See also [677].

Brun's sieve implies $h(x) \to \infty$ as $x\to \infty$.

In [Er85c] Erdős omits the condition that $t$ be even, but this is clearly necessary.

Commonly known as the second Hardy-Littlewood conjecture. In [Er85c] Erdős describes it as 'an old conjecture of mine which was probably already stated by Hardy and Littlewood'.

This is probably false, since Hensley and Richards [HeRi73] have shown that this is false assuming the Hardy-Littlewood prime tuples conjecture.

Erdős [Er85c] reports Straus as remarking that the 'correct way' of stating this conjecture would have been \[\pi(x+y) \leq \pi(x)+2\pi(y/2).\] Clark and Jarvis [ClJa01] have shown this is also incompatible with the prime tuples conjecture.

In [Er85c] Erdős conjectures the weaker result (which in particular follows from the conjecture of Straus) that \[\pi(x+y) \leq \pi(x)+\pi(y)+O\left(\frac{y}{(\log y)^2}\right),\] which the Hensley and Richards result shows (conditionally) would be best possible. Richards conjectured that this is false.

Erdős and Richards further conjectured that the original inequality is true almost always - that is, the set of $x$ such that $\pi(x+y)\leq \pi(x)+\pi(y)$ for all $y<x$ has density $1$. They could only prove that this set has positive lower density.

They also conjectured that for every $x$ the inequality $\pi(x+y)\leq \pi(x)+\pi(y)$ is true provided $y \gg (\log x)^C$ for some large constant $C>0$.

Hardy and Littlewood proved \[\pi(x+y) \leq \pi(x)+O(\pi(y)).\] The best known in this direction is a result of Montgomery and Vaughan [MoVa73], which shows \[\pi(x+y) \leq \pi(x)+2\frac{y}{\log y}.\]

A problem of Erdős and Pomerance [ErPo80], who proved that \[h(n) \ll \frac{n^{3/2}}{(\log n)^{1/2}}.\] Erdős and Selfridge proved $h(n)>(3-o(1))n$, and Ruzsa proved $h(n)/n\to \infty$.

A question of Erdős and Selfridge [ErSe67], who observe that \[\liminf_{n\to \infty}\sum_{0\leq i<k}\omega(n+i)\geq k+\pi(k)-1\] for every $k$. This follows from Pólya's theorem that the set of $k$-smooth integers has unbounded gaps - indeed, $n(n+1)\cdots (n+k-1)$ is divisible by all primes $\leq k$ and, provided $n$ is large, all but at most one of $n,n+1,\ldots,n+k-1$ has a prime factor $>k$ by Pólya's theorem.

It is a classical fact that \[\limsup_{n\to \infty}\omega(n)\frac{\log\log n}{\log n}=1.\]