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

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$.

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

for which every $n-2^k$, \(1<2^k

problem #1142.

3. The values of $f(n)$ are OEIS

A109925.

4. 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}$.

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

\[ E_2(N)

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.

3. 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.

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

exponent scale the average number of prime shifts is bounded.

5. 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.

6. 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$.

7. 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$.

2. 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)

3. 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](https://www.math.okayama-u.ac.jp/mjou/mjou1-46/mjou_pdf/mjou_19/mjou_19_129.pdf),

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$.

4. 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](https://www.math.okayama-u.ac.jp/mjou/mjou1-46/mjou_pdf/mjou_20/mjou_20_041.pdf).

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.

5. 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.

6. 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

2. 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

\[ P_i=\mathbf 1_{\{2i+1\ {\rm is\ prime}\}} \qquad(i\geq0), \]

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

\[ n-2^k=2\bigl(j-2^{k-1}\bigr)+1. \]

Therefore (a)

\[ f(2j+1)=\sum_{k\geq1}P_{j-2^{k-1}} \qquad(2j+1>3), \]

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)

\[ f(n)\leq K-\left\lfloor\frac K{q-1}\right\rfloor+1 \quad(n>3\text{ odd},\ q\nmid n). \]

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).

\[ \boxed{\max_{1\leq n\leq10^9}f(n)=19.} \]

The complete set of maximizers is

\[ \boxed{ 53999715,\quad 194401185,\quad 335200515,\quad 994034415.} \]

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)$:

| $k$ | $p$ | $k$ | $p$ |

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

| 1 | 53999713 | 5 | 53999683 |

| 6 | 53999651 | 7 | 53999587 |

| 8 | 53999459 | 9 | 53999203 |

| 10 | 53998691 | 11 | 53997667 |

| 12 | 53995619 | 14 | 53983331 |

| 17 | 53868643 | 18 | 53737571 |

| 19 | 53475427 | 20 | 52951139 |

| 21 | 51902563 | 22 | 49805411 |

| 23 | 45611107 | 24 | 37222499 |

| 25 | 20445283 | | |

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.

| New record $f(n)$ | First $n$ |

|---:|---:|

| 0 | 1 |

| 1 | 3 |

| 2 | 4 |

| 3 | 15 |

| 4 | 21 |

| 5 | 45 |

| 6 | 75 |

| 7 | 465 |

| 8 | 1095 |

| 9 | 2145 |

| 10 | 4935 |

| 11 | 14955 |

| 12 | 80685 |

| 13 | 229845 |

| 14 | 1295325 |

| 15 | 1575285 |

| 16 | 9700575 |

| 18 | 15054105 |

| 19 | 53999715 |

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

| Value | Number of $n$ |

|---:|---:|

| 15 | 3877 |

| 16 | 894 |

| 17 | 149 |

| 18 | 23 |

| 19 | 4 |

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$.

2. The compressed convolution follows the proved identity in §2.2.

3. Two clean full computations produced identical prime and count

hashes.

4. A separate scalar implementation using elementary trial division

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

5. That scalar implementation also recomputes every record holder and

all four maximizers directly from the definition.

6. 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

\[ H\subseteq\{2,4,\ldots,2^K\} \]

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

\[ R_K(H)=\#\{n\in[2^K,2^{K+1}): n-h\text{ is prime for all }h\in H\}. \]

The elementary union bound (a) is

\[ \#\{n\in[2^K,2^{K+1}):f(n)\geq t\} \leq \sum_{\substack{H\subseteq\{2,\ldots,2^K\}\\|H|=t}}R_K(H). \]

A precise sufficient missing lemma would be a growing-dimension,

uniform prime-tuple bound of the form

\[ R_K(H)\leq 2^K K^{-c t}\exp(o(t\log K)) \tag{*} \]

for some fixed $c>0$, uniformly over all such lacunary $H$.

Indeed, since $\binom Kt\leq2^K$, (*) makes the union bound

\[ \exp\!\bigl(O(K)-c\epsilon K\log K+o(K\log K)\bigr)<1 \]

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.

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