The sieve of Eratosthenes implies that almost all integers are of this form, and the Brun-Selberg sieve implies the number of exceptions in $[1,x]$ is $\ll x/(\log x)^c$ for some constant $c>0$. Erdős [Er79] believed it is 'rather unlikely' that all large integers are of this form.

What if the condition that $p$ is prime is omitted? Selfridge and Wagstaff made a 'preliminary computer search' and suggested that there are infinitely many $n$ not of this form even without the condition that $p$ is prime. It should be true that the number of exceptions in $[1,x]$ is $<x^c$ for some constant $c<1$.

Most generally, given some infinite set $A\subseteq \mathbb{N}$ and function $f:A\to \mathbb{N}$ one can ask for sufficient conditions on $A$ and $f$ that guarantee every large number (or almost all numbers) can be written as\[am^2+b\]for some $m\in A$ and $a\geq 1$ and $0\leq b<f(m)$.

In another direction, one can ask what is the minimal $c_n$ such that $n$ can be written as $n=ap^2+b$ with $0\leq b<c_np$ for some $p\leq \sqrt{n}$. This problem asks whether $c_n\leq 1$ eventually, but in [Er79d] Erdős suggests that in fact $\limsup c_n=\infty$. Is it true that $c_n<n^{o(1)}$?

View the LaTeX source