Is every large integer of the form $ap^2+b$ with $p$ prime, $a\ge1$, $0\le b<p$? (Erdős #676)

Statement

Background

Posed by Erdős [Er79], [Er79d], [Er80, p.107]; listed as open on erdosproblems.com/676 (fetched 2026-07-21, status 'open'). A sieve of Eratosthenes argument shows that almost all integers have this form, and the Brun–Selberg sieve bounds the number of exceptions in $[1,x]$ by $\ll x/(\log x)^c$ for some $c>0$. Erdős nevertheless believed it 'rather unlikely' that every large integer is of this form — that is, he expected infinitely many exceptions. If one drops the requirement that $p$ be prime, Selfridge and Wagstaff reported a 'preliminary computer search' suggesting there are still infinitely many exceptions, and it should hold that the number of exceptions in $[1,x]$ is $<x^c$ for some $c<1$. A related quantitative question fixes $n$ and asks for the least $c_n$ with $n=ap^2+b$, $0\leq b<c_np$, $p\leq\sqrt n$: the present problem asks whether $c_n\leq 1$ eventually, while in [Er79d] Erdős suggests instead that $\limsup c_n=\infty$, and asks whether at least $c_n<n^{o(1)}$. OEIS A390181 records the exceptional integers. The attacker's tool: a computational sieve/search to enumerate the integers not representable and extend the exceptional set (OEIS A390181) and the statistics of $c_n$, together with analytic sieve estimates to sharpen the exponent on the exceptional-set bound.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.