Erdoes #10 - working report - Erdős Problem a Day

Erdős problem #10 — wave 5d report

Access date: 2026-07-26 UTC.

Claim labels used below:

(a) elementary-rigorous: proved in this report from elementary facts.
(b) rigorous-modulo-named-theorem: a theorem in the cited primary source.
(c) plausible/structural-unverified: heuristic, interpretation, or cost estimate.
(d) computational-only: established by the complete finite computation supplied here, not a theorem for unbounded integers.

Outcome

(d) I computed the exact value

\[ A(n):=\min_{\substack{p\leq n\\p\ {\rm prime}}}\operatorname{popcount}(n-p) \]

for every \(2\leq n\leq 1{,}117{,}175{,}146\). The exact distribution is:

| \(A(n)\) | number of \(n\) in the range | first occurrence |

|---:|---:|---:|

| 0 | 56,487,095 | 2 |

| 1 | 515,677,619 | 4 |

| 2 | 502,100,476 | 16 |

| 3 | 42,909,954 | 906 |

| 4 | 1 | 1,117,175,146 |

The counts sum to \(1{,}117{,}175{,}145\), the number of integers in the stated interval.

(a+d) Consequently, the example already displayed on the live problem page,

\[ 1{,}117{,}175{,}146, \]

is in fact the first integer needing four powers of \(2\), under the convention used by the page-linked formal statement (exponents are nonnegative and repetitions are allowed). Explicit minimal representations at the boundary are

\[ \begin{aligned} 1{,}117{,}175{,}145&=1{,}117{,}175{,}107+2+4+32,\\ 1{,}117{,}175{,}146&=1{,}117{,}175{,}107+1+2+4+32. \end{aligned} \]

The checker verifies by trial division that \(1{,}117{,}175{,}107\) is prime, exhausts all representations with at most two powers for the first number and at most three for the second, and proves the absence of any earlier \(A(n)=4\) by a complete packed-bitset sieve.

(d) This is a finite sharp result, not a solution of the open problem. It neither proves a uniform upper bound for all \(n\) nor constructs counterexamples for every fixed bound.

Step 0: mandatory live-page gate

I fetched the live page through the Bright Data cloud-browser route, not by datacenter curl. I also opened its discussion thread through the same browser route.

(d, live-page observation) The exact current statement is:

> Is there some \(k\) such that every large integer is the sum of a prime and at most \(k\) powers of \(2\)?

(d, live-page observation) The page was marked OPEN, last edited 11 April 2026, and displayed:

0 claimed proofs for this problem;
Interested in collaborating — None;
Currently working on this problem — None.

Thus none of the mandatory stop conditions was present.

(d, live-page observation) The page listed references

[Er77c] [Er80,p.96] [ErGr80,p.28] [Er85c] [Er92c] [Er95] [Er97] [Er97c] [Er97e]

and the following known information:

Erdős called the problem “probably unattackable”; the page says Erdős and Graham suggested that no such \(k\) exists, while Erdős elsewhere conjectured with “trepidation” that one does.
Gallagher [Ga75] proved that for every \(\epsilon>0\), some \(k(\epsilon)\) gives lower density at least \(1-\epsilon\).
Granville and Soundararajan [GrSo98] conjectured that three powers suffice for every odd integer and therefore four for every even integer.
The page gives \(1{,}117{,}175{,}146\) as an even integer not representable with at most three powers, and notes the parity-based expectation that infinitely many such even integers may exist.
It points to problems #9, #11, and #16.

(d, live-page observation) The sole discussion comment was not mathematical: it reported a malformed LaTeX spelling of Erdős and a bracket typo, and the thread says the site was updated to address it.

Live source: Erdős Problems #10; discussion: problem #10 thread.

Literature audit

Primary sources that support the page summary

(b) Crocker proved that infinitely many positive odd integers are not a prime plus two positive powers of \(2\). More specifically, his construction simultaneously excludes a prime plus one power and a prime plus two distinct powers; identical powers reduce to one higher power. This supplies the established \(k=2\) obstruction, but it does not address arbitrary fixed \(k\).

Primary source: Roger Crocker, “On the sum of a prime and of two powers of two”, Pacific J. Math. 36 (1971), 103–107, especially Theorem I and the construction on pp. 103–107.

(b) Gallagher's theorem says that the density of odd integers representable as one prime and \(k\) powers of \(2\) tends to \(1\) as \(k\to\infty\). This is the almost-all result quoted by the live page; its quantifiers do not give one fixed \(k\) that handles every sufficiently large integer.

Primary bibliographic source: P. X. Gallagher, “Primes and powers of 2”, Invent. Math. 29 (1975), 125–142, DOI 10.1007/BF01390190. Gallagher's own 1973 announcement states the density theorem explicitly in Notices AMS 20 (1973), abstract 707-A13.

(b) Granville and Soundararajan explicitly conjecture that every odd integer \(>1\) is a prime plus at most three powers of \(2\). Their paper also recalls Crocker's two-power obstruction and Gallagher's density result.

Primary source: Andrew Granville and K. Soundararajan, “A Binary Additive Problem of Erdős and the Order of \(2\bmod p^2\)”, Ramanujan J. 2 (1998), 283–298, DOI 10.1023/A:1009786614584. The relevant conjecture and discussion appear on pp. 285–286.

Relevant work not yet incorporated into the live page

(b) Pan proved that, for every fixed \(\epsilon>0\), there are

\(\gg_\epsilon x^{1-\epsilon}\) odd integers up to \(x\) not of the exact form

\(p+2^a+2^b\). Primary source: Hao Pan,

“On the integers not of the form \(p+2^a+2^b\)”,

arXiv:0905.3809 (2009; published in 2011).

(b) A new paper submitted after the live page's last edit improves Pan's quantitative lower bound. If \(N(x)\) counts odd integers not of the exact form \(p+2^a+2^b\), Ding, Sun, and Zhao prove, for every \(\eta>0\),

\[ N(x)\gg_\eta x\exp\!\left( -(4+\eta)\frac{\log\log\log x}{\log\log x}\log x \right). \]

Primary source: Yuchen Ding, Yu-Chen Sun, and Lilu Zhao,

“An improved lower bound for odd integers not of the form \(p+2^a+2^b\)”,

arXiv:2607.05357v1, submitted 6 July 2026, Theorem 1.1.

(a) These exact-two-power counting theorems do not by themselves settle the present bounded-\(k\) question. They concern \(k=2\), and their counted set can also contain integers representable using zero powers (primes). Crocker's more tailored construction does give infinitely many genuine at-most-two-power exceptions, but neither construction handles every fixed \(k\).

(d, consistency check only) OEIS A156695 lists odd integers not of the exact form \(p+2^a+2^b\), and its initial data include \(1{,}117{,}175{,}145\). OEIS A387053 defines the same minimum \(A(n)\) used here. I treated neither community sequence as a theorem or as input to the computation.

A current citation that does not prove progress on this problem

(b) Johnston and Trudgian's July 2026 revision proves on GRH that every sufficiently large even integer is the sum of two primes and six powers of \(2\). Its Theorem 1 is

\[ n=p_1+p_2+2^{\nu_1}+\cdots+2^{\nu_6}. \]

Primary source: Daniel R. Johnston and Tim Trudgian,

“An update on the Linnik–Goldbach problem”,

arXiv:2605.17825v2, 22 July 2026.

(a) This does not imply a representation by one prime and six powers. A secondary note on A387053 currently attributes an \(A(2n)\leq6\) consequence to that paper, but the displayed primary theorem retains the second prime. I therefore did not count it as a conditional result on Erdős #10.

(c, honest search result) I found no primary source proving any fixed uniform \(k\) for the one-prime problem, conditionally or unconditionally, and no primary source disproving the existence of all such \(k\). This agrees with the live page's OPEN status. The literature search did find the July 2026 exact-two-power improvement above, which postdates the page edit but leaves the main quantifier untouched.

Elementary reductions

The page-linked Lean formalization takes a multiset of natural exponents, so \(2^0=1\) is permitted and repetitions are permitted. The computation uses exactly that convention.

Carrying lemma

(a) For a fixed nonnegative integer \(m\), the least number of powers of \(2\), with repetitions allowed, whose sum is \(m\) is

\[ w_2(m):=\operatorname{popcount}(m). \]

Proof. Repeated equal terms can be carried:

\(2^j+2^j=2^{j+1}\). Repeating this operation terminates with distinct powers and never increases the number of terms. The result is the unique binary expansion of \(m\), which has \(w_2(m)\) terms. Conversely, that binary expansion is a representation with exactly \(w_2(m)\) powers. \(\square\)

It follows immediately that

\[ A(n)=\min_{\substack{p\le n\\p\ {\rm prime}}}w_2(n-p). \]

“Every large integer” versus all integers

(a) Existence of a uniform \(k\) for all sufficiently large integers is equivalent to boundedness of \(A(n)\) over all \(n\ge2\). One direction is immediate. For the other, every individual \(n\ge2\) has the representation

\[ n=2+(n-2), \]

with \(n-2\) expanded in binary. Hence every finite exceptional prefix has a finite maximum \(A(n)\), which can be absorbed into the eventual bound.

Exact odd/even reduction

For odd \(o\), define

\[ b(o):=\min_{\substack{p\le o\\p\ {\rm odd\ prime}}}w_2(o-p), \]

with \(b(o)=\infty\) if no such prime exists.

(a) For odd \(o\ge3\) and even \(e=o+1\),

\[ \boxed{A(o)=\min\{b(o),w_2(o-2)\}}, \qquad \boxed{A(e)=\min\{1+b(o),w_2(e-2)\}}. \]

Proof. The second entry in each minimum is exactly the option \(p=2\). If \(p\) is odd, then \(o-p\) is even. For the even successor, \(e-p\) is odd, so its binary bit \(2^0\) is present and

\[ w_2(e-p)=1+w_2(e-p-1)=1+w_2(o-p). \]

Minimizing over odd primes gives the formulas. \(\square\)

(a) In particular, a fixed bound \(k\) for all sufficiently large odd integers gives \(k+1\) for all sufficiently large even integers by adding \(2^0\). Thus the original existence problem is equivalent to its odd-integer restriction, up to increasing the bound by one.

Complete finite computation

Let

\[ B=1{,}117{,}175{,}145,\qquad M=(B+1)/2=558{,}587{,}573. \]

Index odd integers by \(o=2i+1\), \(0\le i

(a) Since

\[ \frac{o-p}{2}=i-j \quad\text{and}\quad w_2(o-p)=w_2(i-j), \]

odd \(o\) has an odd-prime representation with at most \(r\) powers exactly when the odd-prime bitset \(P\), shifted left by some \(d\) with \(w_2(d)\le r\), contains bit \(i\). Thus

\[ C_r=\bigvee_{\substack{dis an exact certificate, not a probabilistic search.

The verifier:

1. constructs \(P\) with the Eratosthenes sieve on odd integers;

2. packs \(P\) into 64-bit words;

3. constructs \(C_1\) using all one-bit shifts;

4. constructs \(C_2\) using all valid two-bit shifts (431 such shifts at this bound);

5. finds the first clear valid bit of \(C_2\);

6. separately enumerates every canonical offset of weight at most two or three at the boundary and checks primality by trial division;

7. incorporates the sparse \(p=2\) cases exactly and counts every \(A(n)\).

The packed certificate statistics are:

| item | exact value |

|---|---:|

| odd-prime bits through \(B\) | 56,487,094 |

| odd indices covered with \(\le1\) power and an odd prime | 515,677,594 |

| odd indices covered with \(\le2\) powers and an odd prime | 558,587,571 |

| total odd indices \(M\) | 558,587,573 |

(d) The two bits absent from \(C_2\) are the invalid index for \(o=1\) and the final index

\[ o=B=1{,}117{,}175{,}145. \]

Therefore every odd \(3\le o

(d) Direct enumeration finds

\[ B=1{,}117{,}175{,}107+2^1+2^2+2^5, \]

so \(b(B)=3\).

(a+d) Let \(E=B+1\). If an odd prime represented \(E\) with at most three powers, the canonical binary offset would be odd. Removing its compulsory \(2^0\) bit would give an odd-prime representation of \(B\) with at most two powers, contradicting the exhaustive \(C_2\) certificate. The only remaining prime is \(2\), but

\[ w_2(E-2)=w_2(1{,}117{,}175{,}144)=15>3. \]

Thus \(A(E)>3\). Adding \(2^0\) to the displayed representation of \(B\) gives \(A(E)\le4\), hence \(A(E)=4\).

(a+d) For every smaller even \(4\le e=o+1

Reproduction and independent checks

The standalone verifier is erdos10_wave5d_verify.py. It is deliberately a different implementation from the OpenMP scanner: it uses a NumPy Eratosthenes sieve and vectorized packed-word shifts, then recomputes the boundary candidates with independent trial-division primality tests.

Run:

python runs/erdos10_wave5d_verify.py

Observed output:

verified range: 2 <= n <= 1117175146
odd-prime sieve count: 56487094
weight-1 odd coverage: 515677594
weight-2 odd coverage: 558587571
first odd-prime weight-2 gap: 1117175145
boundary witnesses: 1117175145=1117175107+2+4+32; 1117175146=1117175107+1+2+4+32
a(n) exact counts for a=0,1,2,3,4: [56487095, 515677619, 502100476, 42909954, 1]
first occurrences for a=0,1,2,3,4: [2, 4, 16, 906, 1117175146]
PASS

On this VM the independent run took 22.35 seconds and peaked at 709,512 KiB RSS.

The faster, separately written OpenMP implementation is erdos10_scan.cpp. Reproduce it with:

g++ -O3 -march=native -std=c++20 -fopenmp \
  -o /tmp/erdos10_scan runs/erdos10_scan.cpp
OMP_NUM_THREADS=16 /tmp/erdos10_scan 1117175145

It produced the same counts and boundary in 16.49 seconds. Neither implementation reads OEIS data or a precomputed prime table.

What remains, exactly

For \(n<2^L\), the number of candidate offsets with at most fixed \(k\) binary ones is only

\[ \sum_{j=0}^{k}\binom Lj=O_k((\log n)^k). \]

(a) Closing the problem affirmatively requires a fixed \(k\) and a uniform, pointwise result

\[ \sum_{\substack{0\le s\le n-2\\w_2(s)\le k}} 1_{\mathbb P}(n-s)>0 \qquad\text{for every sufficiently large }n. \]

Gallagher supplies an averaged density statement after \(k\) is chosen as a function of an allowed exceptional density. It does not remove the exceptional set for any one \(k\).

(c) The exact missing analytic ingredient is therefore a worst-case prime-detection theorem in the \(n\)-dependent polylogarithmic set

\[ \{\,n-s: w_2(s)\le k\,\}. \]

Available sieve/circle-method estimates average over \(n\); at this polylogarithmic sample size their errors do not yield positivity for every individual \(n\). Treating the candidates as independent primes predicts many representations for \(k\ge2\), but Crocker-type covering congruences show that the required independence is false in precisely the dangerous direction.

(a) Closing the problem negatively requires something different and equally uniform: for every fixed \(k\), arbitrarily large \(n\) for which every \(n-s\), \(w_2(s)\le k\), is composite. Crocker's congruence construction handles two powers. The July 2026 work greatly increases the known count for failures of the exact two-power form, but neither provides compatible covering congruences for all \(k\).

(c, cost estimate) Merely extending this dense \(k=2\) computation to \(10^{12}\) would not help with the uniform step. One packed odd bitset at that scale is about 62.5 GB; several dense bitsets do not fit this 62 GiB VM. A segmented version should cost roughly 100–200 core-hours (about 8–12 wall-hours on 16 comparable cores, or roughly USD 5–20 at USD 0.05–0.10/core-hour). Even an arbitrarily larger finite cutoff cannot prove the required “for every sufficiently large \(n\)” assertion.

PARTIAL: exact exhaustive table through 1,117,175,146; proved computationally that 1,117,175,146 is the first integer requiring four powers, while the uniform boundedness question remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger