Are there infinitely many $n$ such that $n-k^2$ is prime for all $k$ with $(n,k)=1$ and $k^2<n$?
In \cite{Va99} it is asked whether $968$ is the largest integer with this property, but this is an error, since for example $968-9=7\cdot 137$.
The list of $n$ satisfying the given property is
A214583 in the OEIS. The largest known such $n$ is $1722$.
ChatGPT and Tang
have shown that the number of such $n$ in $[1,N]$ is at most $N^{1/2+o(1)}$.
An internal OpenAI model (see \cite{APSSV26b}) has resolved this, proving that for any integer $a\geq 1$ there are only finitely many $n$ such that $n-ak^2$ is prime for all $k$ with $(k,n)=1$ and $ak^2<n$, deducing this from a result of Pollack \cite{Po17}.
See also
[1140] and
[1142].
References
[APSSV26b] B. Alexeev, M. Putterman, M. Sawhney, M. Sellke, and G. Valiant, Short proofs in combinatorics, probability, and number theory II. arXiv:2604.06609 (2026).
[Po17] Pollack, Paul, Bounds for the first several prime character nonresidues. Proc. Amer. Math. Soc. (2017), 2815--2826.
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erd\H{o}s and his mathematics", Budapest, July 1999 (1999).
