Erdős problem #236 — live-page audit, exact search, and the remaining sieve wall

Access/research date: 2026-07-26 UTC.

Claim labels used throughout:

• (a) elementary-rigorous: a complete proof is given here.
• (b) rigorous-modulo-named-theorem: this is a statement from the cited source.
• (c) plausible/structural-unverified: heuristic or diagnosis, not a theorem.
• (d) computational-only: an exhaustive finite computation, not an asymptotic result.

0. Mandatory live-page gate

I fetched the rendered live page and its discussion thread with the Bright Data residential browser, not datacenter curl. The screenshot used for the audit was /tmp/erdos236-live.png.

The live page's statement, verbatim, is:

Let \(f(n)\) count the number of solutions to \(n=p+2^k\) for prime \(p\) and \(k\geq 0\). Is it true that \(f(n)=o(\log n)\)?

Live status and collision markers:

• Status: OPEN.
• Last page edit: 23 January 2026.
• Claimed proofs: 0.
• “Currently working on this problem”: None.
• “Interested in collaborating”: None.
• The page has seven comments.

Thus the mandatory stop condition does not apply.

The results listed on the problem page are:

1. (b) Erdős [Er50] proved that \(f(n)\gg\log\log n\) for

infinitely many \(n\).

1. (b) Erdős could not prove that there are not infinitely many \(n\)

for which every \(n-2^k\), \(1<2^k<n\), is prime; the page points to problem #1142.

1. The values of \(f(n)\) are OEIS

A109925.

1. The page points to related problem #237.

The page cites the following original Erdős sources:

• [Er55c] P. Erdős, *Some problems on the distribution of prime

numbers*, C.I.M.E., Teoria dei numeri (1955).

• [Er61] P. Erdős, Some unsolved problems, Magyar Tud. Akad. Mat.

Kutató Int. Közl. (1961), 221–254, MR 177846.

• [Er77c] P. Erdős, *Problems and results on combinatorial number

theory. III*, Number Theory Day (1977), 43–72, MR 472752.

• [Er50] P. Erdős, *On integers of the form \(2^k+p\) and some related

problems*, Summa Brasil. Math. 2 (1950), 113–123, MR 44558.

All seven live comments

The site explicitly warns that comments are not verified. I read all seven; the following is a faithful content audit, not an endorsement.

1. Alfaiz, 2025-11-25. For the stronger all-shifts-prime problem,

reports Hooley's ERH-conditional \(O(x^{1-\lambda+\epsilon})\) bound, where \(\lambda=\prod_p(1-1/(p(p-1)))\), Narkiewicz's improvement to \(O(x^{1-\lambda/\log 2+\epsilon})\), and the Uchiyama–Yorinaga verification that there is no further example through \(2^{77}\).

1. Alfaiz, 2025-11-18. Reports Vaughan's unconditional bound

\[ E_2(N)<N\exp\!\left( -\frac{c\log N\log\log\log N}{\log\log N}\right) \] for the count of all-shifts-prime \(n\leq N\), and reports that Mientka–Weitzenkamp found only \(7,15,21,45,75,105\) through \(2^{44}\). The comment says the site was updated.

1. TerenceTao, 2025-09-29 03:21. Says probabilistic heuristics

suggest the answer to #236 is true, but only barely, and a proof appears beyond current technology.

1. StijnC, 06:13. Asks why “barely,” noting that on a dyadic

exponent scale the average number of prime shifts is bounded.

1. TerenceTao, 06:37. Explains that requiring all \(K\) candidates

prime has heuristic probability about \(K^{-K}\), versus about \(2^K\) possible \(n\) at that scale.

1. StijnC, 07:06. Notes that this makes very large all-prime

examples heuristically very unlikely and suggests a Poisson calculation for the event \(f(n)>c\log K\).

1. TerenceTao, 15:17. Clarifies that “barely” refers to the

precision needed: even an exceptionally strong-looking upper bound of shape \(\exp(-K/\log K)\) would still be inadequate to prove finiteness when the heuristic is \(\exp(-K\log K)\).

None of these comments claims a proof of #236, and neither conditional result about the all-shifts-prime set supplies the requested pointwise \(o(\log n)\) bound.

1. Primary-source search

What was verified

1. Erdős 1950. The archival scan is

here. I OCRed the paper itself. It explicitly says, “It can be conjectured that \(f(n)=o(\log n)\). This if true is probably rather deep.” Its Theorem 1 proves (b) \[ f(n)>c\log\log n \quad\text{for infinitely many }n. \] Its Theorem 2 proves (b) that for every fixed positive integer \(r\), \[ \limsup_{x\to\infty}\frac1x\sum_{n\leq x}f(n)^r<\infty. \] Fixed moments give strong average/tail information but no pointwise maximum bound when \(r\) must grow with \(\log x\).

1. Erdős 1977. In

Problems and results on combinatorial number theory III, Erdős again writes that he “could not decide whether \(f(n)=o(\log n)\)” and says it is “extremely doubtful” that covering congruences will help. (b)

1. Uchiyama–Yorinaga I. The primary paper is

S. Uchiyama and M. Yorinaga, Notes on a conjecture of P. Erdős. I, Math. J. Okayama Univ. 19 (1977), 129–140, DOI 10.18926/mjou/33403. It explicitly formulates \(f(n;1,b)=o(\log n)\) for every fixed \(b\geq2\) and says it “seems difficult to prove (or disprove).” It proves a generalized \(\gg\log\log n\) lower bound and constructs a positive-density set on which \(f(n;a,b)=0\). (b) It also gives the finite all-shifts-prime exclusion through \[ 152246817378604933869885>2^{77}; \] this is a different, stronger-at-each-point question, not a maximum table for \(f\).

1. Uchiyama–Yorinaga II. The continuation is

M. Yorinaga and S. Uchiyama, Notes on a conjecture of P. Erdős. II, Math. J. Okayama Univ. 20 (1978), 41–49. It proves, for fixed \(b\geq2\), (b) \[ \lim_{N\to\infty}\frac1N\sum_{n\leq N}f(n;1,b)=\frac1{\log b}. \] At \(b=2\) the mean is \(1/\log2=1.442695\ldots\). Their convention starts at \(k=1\); adding the page's \(k=0\) term does not change the limiting mean.

1. The all-shifts-prime literature. I verified the metadata and

statements relevant to the comments:

• R. C. Vaughan,

Some applications of Montgomery's sieve90059-0), J. Number Theory 5 (1973), 64–79.

• W. Narkiewicz,

On a conjecture of Erdős, Colloq. Math. 37 (1977), 313–315. I OCRed the primary three-page paper; it states Vaughan's unconditional estimate and proves the ERH-conditional exponent \(1-\lambda/\log2+\epsilon\).

• W. E. Mientka and R. C. Weitzenkamp,

On \(f\)-plentiful numbers80067-0), J. Combin. Theory 7 (1969), 374–377.

1. OEIS. A109925 links a table only for \(1\leq n\leq10{,}000\).

It confirms the definition and the initial values, but it does not contain the extremal range computed below.

Honest search miss

Exact-phrase searches for the conjecture, \(f(n;1,b)=o(\log n)\), and “number of primes of the form \(n-2^k\)” found the original Erdős papers, the two Uchiyama–Yorinaga papers, and sources about the all-shifts-prime subproblem. I found no later primary source proving a pointwise upper bound \(o(\log n)\), conditional or unconditional. This is a search result, not proof that no such paper exists. It agrees with the live page's OPEN status.

2. Elementary reductions

2.1 Parity removes half the search

Claim (a). If \(n\) is even, then \(f(n)\leq2\).

For \(k=0\), there is at most the one candidate \(n-1\). For every \(k\geq1\), \(n-2^k\) is even, hence can be prime only if it equals

1. The equation \(n-2^k=2\) has at most one \(k\). This proves the

claim.

If \(n>3\) is odd, the \(k=0\) difference \(n-1\) is even and greater than 2, so it contributes nothing. Consequently every value \(f(n)\geq3\) occurs at an odd \(n\) and is counted entirely by \(k\geq1\).

2.2 Exact compressed convolution

Let

with \(P_0=0\). Write an odd \(n\) as \(n=2j+1\). For \(k\geq1\),

Therefore (a)

where negative indices contribute zero. This identity is why one Eratosthenes sieve and 29 byte-array shifts exhaust every \(n\leq10^9\); there is no probable-prime test in the exhaustive stage.

2.3 What primitive-root congruences do and do not give

Let \(K=\lfloor\log_2(n-2)\rfloor\), let \(q\) be an odd prime for which 2 is a primitive root, and suppose \(q\nmid n\). There is one residue \(r\bmod(q-1)\) with \(2^r\equiv n\pmod q\). Every \(k\leq K\) in this residue class makes \(q\mid n-2^k\); at most one of those differences can itself equal \(q\). Hence (a)

For \(q=3\), for example, this gives essentially a one-half saving unless \(3\mid n\). This is effective for the near-all-prime problem: a sufficiently prime-rich \(n\) is forced to be divisible by critical primes. It does not yield \(o(K)\), because a candidate sequence can make every \(n\) divisible by any fixed finite product of such primes. Letting the prime set grow introduces correlated residue classes modulo the orders \(\operatorname{ord}_q(2)\), exactly where the simple covering argument stops.

3. Exact result through \(10^9\)

3.1 The result

Computational theorem (d).

The complete set of maximizers is

There is no \(n\leq10^9\) with \(f(n)\geq20\).

For an explicit 19-representation example, \(n=53999715\) works at the following \((k,p=n-2^k)\):

The standalone checker independently proves primality of every entry in this table by trial division and also verifies that every omitted exponent gives a nonprime difference. (d)

3.2 Exact running-record table

Here “first \(n\)” means the least integer where the running maximum strictly increases. The jump from 16 directly to 18 is real.

The exact high-value histogram on \(1\leq n\leq10^9\) is:

All these \(n\) are odd by the parity lemma, so the odd-array histogram is also the all-integer histogram at these values.

3.3 Verification protocol

The standalone verifier is verify_erdos236_wave5n.py. It requires NumPy and defaults to the full \(10^9\) run.

The final clean execution gave:

limit=1000000000
pi(limit)=50847534
powers k>=1 used=29
prime_flags_sha256=74d176c4598da9365337436398bedd09312587810e7355be4038cebb449d804f
odd_f_counts_sha256=b1831159a49e7891e82f7a73dfbbd428a6e7eaa264658628c9a6a07bec5c490c
maximum=19
maximizers=53999715 194401185 335200515 994034415
independent scalar checks (all n<=10,000 and every reported point): PASS
reference assertions: PASS
elapsed_seconds=23.245
maxrss=1072004KB

The safeguards are:

1. A classical odd-only Eratosthenes sieve exactly recomputes all

primes through \(10^9\).

1. The compressed convolution follows the proved identity in §2.2.
2. Two clean full computations produced identical prime and count

hashes.

1. A separate scalar implementation using elementary trial division

checks the convolution value for every \(n\leq10{,}000\).

1. That scalar implementation also recomputes every record holder and

all four maximizers directly from the definition.

1. The independently reproduced \(\pi(10^9)=50847534\) is an extra

whole-sieve checksum.

The core exhaustive calculation is:

import math
import numpy as np

N = 1_000_000_000
m = (N + 1) // 2                 # indices represent 1,3,5,...
prime = np.ones(m, dtype=np.bool_)
prime[0] = False
for p in range(3, math.isqrt(N) + 1, 2):
    if prime[p // 2]:
        prime[(p * p) // 2::p] = False

count = np.zeros(m, dtype=np.uint8)
k = 1
while (offset := 1 << (k - 1)) < m:
    count[offset:] += prime[:-offset]
    k += 1

maximum = int(count.max())        # even n have f(n) <= 2
maximizers = []
block_size = 8_000_000
for start in range(0, m, block_size):
    block = count[start:start + block_size]
    loc = np.flatnonzero(block == maximum)
    maximizers += (2 * (loc + start) + 1).tolist()

print(maximum, maximizers)

The linked verifier contains the record scan, hashes, histogram, reference assertions, and independent scalar checker as well.

4. Exact remaining reduction and why standard machinery stalls

Let \(2^K\leq n<2^{K+1}\), and fix \(\epsilon>0\). If \(f(n)\geq t=\lceil\epsilon K\rceil\), then some \(t\)-element subset

has \(n-h\) prime for every \(h\in H\). Define

The elementary union bound (a) is

A precise sufficient missing lemma would be a growing-dimension, uniform prime-tuple bound of the form

for some fixed \(c>0\), uniformly over all such lacunary \(H\). Indeed, since \(\binom Kt\leq2^K\), (*) makes the union bound

for all sufficiently large \(K\), proving \(f(n)<\epsilon K\). Thus (*) would settle the problem. **(a), conditional on (*)**

The exact technical wall is uniformity in the sieve dimension \(t\asymp K\asymp\log n\). Fixed-dimensional Brun/Selberg upper sieves have constants with factorial growth in \(t\). At \(t\asymp K\), a \(t!\) loss is \(\exp((1+o(1))t\log K)\), the same size as the entire \(K^{-t}\) primality saving needed in (*). It therefore cancels the decisive term rather than leaving \(K^{-ct}\). Erdős's fixed-moment Theorem 2 is consistent with this: every fixed moment is controlled, but its constants are not uniform for a moment order growing like \(\log n\). (c)

An equivalent small-prime formulation makes the same obstruction concrete. It would suffice to find \(B(K)\) such that uniformly for all \(n\in[2^K,2^{K+1})\), all but \(o(K)\) of the differences \(n-2^k\) have a proper prime divisor at most \(B(K)\). The residue sets are governed by \(\operatorname{ord}_q(2)\), are highly correlated, and disappear entirely when \(q\mid n\). No source found in the search supplies this uniform covering lemma. (a) as a reduction; (c) as a statement about current methods

This is why neither:

• the constant average \(1/\log2\),
• all fixed moments,
• the strong density estimate for the all-shifts-prime exceptional

set, nor

• a much larger finite search

closes the pointwise limit. The missing finiteness/uniformity step is exactly a high-dimensional prime-tuple upper bound such as (*), not more data about typical \(n\).

For scale: extrapolating the verified dense computation linearly from \(10^9\) to \(10^{12}\) gives about 6.5 memory-bandwidth hours and about 1 TB for the two raw dense byte arrays. A segmented implementation would reduce memory to a few GB but still cost roughly 6–15 core-hours (about \$0.30–\$3 at \$0.05–\$0.20/core-hour, before high-memory-instance overhead). Such a run could extend the finite table but cannot address the uniform asymptotic lemma, so it was not run here.

PARTIAL: Exact exhaustive computation proves max_{n<=10^9} f(n)=19 with four maximizers and a reproducible checker; the open asymptotic reduces to a growing-dimension uniform prime-tuple sieve bound whose factorial loss is the precise current wall.