Is the number of representations $n=p+2^k$ always $o(\log n)$? (Erdős #236)
Statement
For a positive integer $n$, let $f(n)$ be the number of representations of $n$ in the form $n=p+2^k$, where $p$ is a prime and $k\ge 0$ is an integer (so $2^k\in\{1,2,4,8,\ldots\}$). Is it true that $f(n)=o(\log n)$ as $n\to\infty$; that is, does $f(n)/\log n\to 0$?
Acceptance. FULLY RESOLVES: a complete proof that $f(n)=o(\log n)$ (i.e. $f(n)/\log n\to 0$), or a disproof (a proof that $\limsup_n f(n)/\log n>0$) — machine-checkable (Lean/Coq) preferred, otherwise a full written proof. ADVANCES (each a complete proof, strictly beyond the background): any nontrivial unconditional upper bound of the form $f(n)\le(1-\delta)\log_2 n$ for a fixed $\delta>0$ and all large $n$, or $f(n)\ll\log n/\psi(n)$ for some explicit $\psi(n)\to\infty$; or an improvement of Erdős's infinitely-often lower bound $f(n)\gg\log\log n$ to a larger proven growth rate; or a proof resolving the related clustering question of whether infinitely many $n$ satisfy that $n-2^k$ is prime for all $1<2^k<n$. Deliver a machine-checkable or complete written proof.
Background
Posed by Erdős [Er55c], [Er61], [Er77c]; listed as open on erdosproblems.com/236 (fetched 2026-07-21, status 'open'). Since only exponents $k$ with $2^k<n$ can contribute, one has the trivial bound $f(n)\le\log_2 n+O(1)$, so the conjecture $f(n)=o(\log n)$ asks that the number of such representations is always negligible compared with this maximum. Erdős [Er50] proved a matching-order lower bound infinitely often: there are infinitely many $n$ with $f(n)\gg\log\log n$. Erdős remarked that he could not even rule out the existence of infinitely many $n$ for which $n-2^k$ is prime for every $k$ with $1<2^k<n$ (a stronger clustering, related to erdosproblems.com/1142). The values of $f(n)$ are OEIS A109925 (and A039669 lists the related integers $n$ for which $n-2^k$ is prime for every $k\ge 1$ with $2^k<n$, tied to the clustering remark above), and the statement has a Lean formalization in the formal-conjectures project; no Erdős prize is attached. Attacker's tool: sieve and analytic estimates for representations as a prime plus a power of two (Romanoff-, Erdős-, and Crocker-type arguments); direct computation of $f(n)$ to locate record multiplicities and to test the $o(\log n)$ growth empirically (A109925).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #236 (T. F. Bloom) | website |
| REF-02 | OEIS A109925 — number of representations of n as prime + power of 2 | website |
| REF-03 | OEIS A039669 — numbers n such that n − 2^k is prime for all k ≥ 1 with 2^k < n | website |
| REF-04 | Lean formalisation (formal-conjectures, Erdős #236) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.