SOLVED - $10000

For any $C>0$ are there infinitely many $n$ such that
\[p_{n+1}-p_n> C\frac{\log\log n\log\log\log\log n}{(\log\log \log n)^2}\log n?\]

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].

OPEN

Let $C\geq 0$. Is there an infinite sequence of $n_i$ such that
\[\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C?\]

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.

SOLVED - $100

Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?

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}.\]

OPEN

Let $A$ be the set of all integers not of the form $p+2^{k}+2^l$ (where $k,l\geq 0$ and $p$ is prime). Is the upper density of $A$ positive?

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.

OPEN

Is there some $k$ such that every integer is the sum of a prime and at most $k$ powers of 2?

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$).

OPEN

Is it true that
\[\sum_{n=1}^\infty(-1)^n\frac{n}{p_n}\]
converges, where $p_n$ is the sequence of primes?

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.

SOLVED

Is the set of odd integers not of the form $2^k+p$ the union of an infinite arithmetic progression and a set of density $0$?

OPEN

Are there infinitely many primes $p$ such that every even number $n\leq p-3$ can be written as a difference of primes $n=q_1-q_2$ where $q_1,q_2\leq p$?

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$.

SOLVED

Let $A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}$ be such that $\phi(a_1)<\cdots<\phi(a_t)$. The primes are such an example. Are they the largest possible? Can one show that $\lvert A\rvert<(1+o(1))\pi(N)$ or even $\lvert A\rvert=o(N)$?

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)$.

OPEN

Is there an integer $m$ with $(m,6)=1$ such that none of $2^k3^\ell m+1$ are prime, for any $k,\ell\geq 0$?

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$.

OPEN

Let $d_n=p_{n+1}-p_n$. The set of $n$ such that $d_{n+1}\geq d_n$ has density $1/2$, and similarly for $d_{n+1}\leq d_n$. Furthermore, there are infinitely many $n$ such that $d_{n+1}=d_n$.

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

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.

OPEN

Let $f(n)$ count the number of solutions to $n=p+2^k$ for prime $p$ and $k\geq 0$. Is it true that $f(n)=o(\log n)$?

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 $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].

SOLVED

Let $A\subseteq \mathbb{N}$ be a set such that $\lvert A\cap \{1,\ldots,N\}\rvert \gg \log N$ for all large $N$. Let $f(n)$ count the number of solutions to $n=p+a$ for $p$ prime and $a\in A$. Is it true that $\limsup f(n)=\infty$?

OPEN

Is there an infinite set of primes $P$ such that if $\{a_1<a_2<\cdots\}$ is the set of integers divisible only by primes in $P$ then $\lim a_{i+1}-a_i=\infty$?

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.

OPEN

Let $k\geq 3$. Is there a choice of congruence classes $a_p\pmod{p}$ for every prime $p$ such that all except finitely many integers can be written as $a_p+tp$ for some prime $p$ and integer $t\geq k$?

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.

OPEN

Is there a sequence $A=\{1\leq a_1<a_2<\cdots\}$ such that every integer is the sum of some finite number of consecutive elements of $A$? Can the number of representations of $n$ in this form tend to infinity with $n$?

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.

SOLVED

Is it true that, for every $n$ and $d$, there exists $k$ such that
\[d \mid p_{n+1}+\cdots+p_{n+k},\]
where $p_r$ denotes the $r$th prime?

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+r-1}.\]

OPEN

Is there a set $A\subseteq \mathbb{N}$ such that, for infinitely many $n$, all of $n-a$ are prime for all $a\in A$ with $0<a<n$ and
\[\liminf\frac{\lvert A\cap [1,x]\rvert}{\pi(x)}>0?\]

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

OPEN

Are there two infinite sets $A$ and $B$ such that $A+B$ agrees with the set of prime numbers up to finitely many exceptions?

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].

OPEN

Let $[1,\ldots,n]$ denote the least common multiple of $\{1,\ldots,n\}$. Is it true that, for all $k\geq 1$,
\[[1,\ldots,p_{k+1}-1]< p_k[1,\ldots,p_k]?\]

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.

OPEN

Let $s_t(n)$ be the $t$-smooth component of $n$ - that is, the product of all primes $p$ (with multiplicity) dividing $n$ such that $p<t$. Let $f(n,t)$ count the number of distinct possible values for $s_t(m)$ for $m\in [n+1,n+t]$. Is there an $\epsilon>0$ such that
\[f(n,t)>\epsilon t\]
for all $t$ and $n$?

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

OPEN

Let $p(n)$ denote the least prime factor of $n$. There is a constant $c>0$ such that
\[\sum_{\substack{n<x\\ n\textrm{ not prime}}}\frac{p(n)}{n}\sim c\frac{x^{1/2}}{(\log x)^2}.\]
Is it true that there exists a constant $C>0$ such that
\[\sum_{x\leq n\leq x+Cx^{1/2}(\log x)^2}\frac{p(n)}{n} \gg 1\]
for all large $x$?

OPEN

Is it true that, for all sufficiently large $n$, there exists some $k$ such that
\[p(n+k)>k^2+1,\]
where $p(m)$ denotes the least prime factor of $m$?

Can one prove this is false if we replace $k^2+1$ by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$, for all $\epsilon>0$, where $C_\epsilon>0$ is some constant?

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$.

OPEN

Is it true that for all large $n$ there exists $k$ such that $n+k$ is composite and
\[p(n+k)>k^2,\]
where $p(m)$ is the least prime factor of $m$?

OPEN

Is it true that for almost all $n$ there exists some $m\in (p_n,p_{n+1})$ such that
\[p(m) \geq p_{n+1}-p_n,\]
where $p(m)$ denotes the least prime factor of $m$?

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.

OPEN

Is it true that for every $0\leq k\leq n$ the largest prime divisor of $\binom{n}{k}$ is
\[> \min(n-k+1, k^{1+c})\]
for some constant $c>0$?

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$.

OPEN

For $0\leq k\leq n$ write
\[\binom{n}{k} = uv\]
where the only primes dividing $u$ are in $[2,k]$ and the only primes dividing $v$ are in $(k,n]$.

Let $f(n)$ be the smallest $k$ such that $u>n^2$. Give bounds for $f(n)$.

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$.

OPEN

Let $\epsilon>0$ and $n$ be large depending on $\epsilon$. Is it true that for all $n^\epsilon<k\leq n^{1-\epsilon}$ the number of distinct prime divisors of $\binom{n}{k}$ is
\[(1+o(1))k\sum_{k<p<n}\frac{1}{p}?\]
Or perhaps even when $k \geq (\log n)^c$?

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)}$.

OPEN

Let $n\geq 1$ and $p_1<\cdots<p_n$ denote the first $n$ primes. Let $P=\prod_{1\leq i\leq n}p_i$. Does there always exist some prime $p$ with $p_n<p<P$ such that $P+p$ is prime?

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$.

OPEN

Can there exist two distinct integers $x$ and $y$ such that $x,y$ have the same prime factors, $x+1,y+1$ have the same prime factors, and $x+2,y+2$ also have the same prime factors?

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].

OPEN

Let $d_n=p_{n+1}-p_n$, where $p_n$ is the $n$th prime. Let $h(x)$ be maximal such that for some $n<x$ the numbers $d_n,d_{n+1},\ldots,d_{n+h(x)-1}$ are all distinct. Estimate $h(x)$. In particular, is it true that
\[h(x) >(\log x)^c\]
for some constant $c>0$, and
\[h(x)=o(\log x)?\]

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

OPEN

Let $d_n=p_{n+1}-p_n$, where $p_n$ is the $n$th prime. Let $r(x)$ be the smallest even integer $t$ such that $d_n=t$ has no solutions for $n\leq x$.

Is it true that $r(x)\to \infty$? Or even $r(x)/\log x \to \infty$?

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

OPEN

If $\pi(x)$ counts the number of primes in $[1,x]$ then is it true that
\[\pi(x+y) \leq \pi(x)+\pi(y)?\]

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}.\]