Integers $n>105$ with $n-2^k$ prime for all $1<2^k<n$: any, or infinitely many? (Erdős #1142)
Statement
Are there infinitely many positive integers $n$ — or indeed any $n>105$ at all — such that $n-2^k$ is prime for every power of two with $1<2^k<n$?
Acceptance. FULLY RESOLVES: EITHER exhibit a specific integer $n>105$ together with the list of all powers $2^k$ with $1<2^k<n$ and a primality certificate for each $n-2^k$ (a fully machine-checkable witness), answering the 'any $n>105$' question; OR a proof that there are infinitely many such $n$; OR a proof that $105$ is the largest (equivalently that no $n>105$ exists). ADVANCES: extend the exhaustive verified bound beyond the best stated in background (currently no such $n$ up to $2^{44}$) to a new record $N$, with the search program and a reproducible certificate of exhaustiveness over $(105,N]$; or improve Vaughan's upper bound on the counting function; or prove Erdős's $o(\log n)$ conjecture on the number of prime values among $n-2^k$. Deliver the witness with its primality certificates, or the search code plus the attained exhaustiveness bound.
Background
Attributed to Erdős and recorded by Vaughan [Va99, §1.7]; also problem A19 in Guy's 'Unsolved Problems in Number Theory' [Gu04]; listed as open on erdosproblems.com/1142 (fetched 2026-07-21, status 'open'). The only known such $n$ are $4,7,15,21,45,75,105$ (OEIS A039669), and it is widely expected that $105$ is the largest. Mientka and Weitzenkamp [MiWe69] proved there is no further such $n$ up to $2^{44}$. Vaughan [Va73] showed the number of $n\leq N$ with the property is at most $\exp\!\left(-c\,\frac{\log\log\log N}{\log\log N}\log N\right)N$ for some constant $c>0$. Erdős made the stronger conjecture (see erdosproblems.com/236) that the number of $k$ with $1<2^k<n$ for which $n-2^k$ is prime is $o(\log n)$. No cash prize is attached. Attacker's tool: extend the exhaustive verified search beyond $2^{44}$ — for each $n$, test primality of $n-2^k$ across the $\lfloor\log_2 n\rfloor$ relevant powers using fast sieving and probable-prime tests — recording either a genuine $n>105$ (a finite, fully checkable witness) or a new exhaustiveness bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1142 (T. F. Bloom) | website |
| REF-02 | OEIS A039669 — n such that n-2^k is prime for all 1<2^k<n | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.