Erdős problem #1142 — live audit and an exact interval beyond \(2^{128}\)

Access/search date: 2026-07-27 UTC.

Result in one paragraph

The mandatory live-page gate did not fire: the problem is OPEN, there are 0 claimed proofs, and both the “currently working” and “interested in collaborating” fields say None. I do not solve the uniform problem. I do prove by an exact, reproducible modular covering that there is no solution in the concrete interval

The upper endpoint is

The computation tests five billion consecutive reduced multipliers, has zero survivors, and never invokes a probable-prime test. Every rejection has a proper prime divisor at most \(997\). The standalone verifier was run twice over the full range; both runs produced the same SHA-256 covering certificate. [D, supported by the elementary reduction [A] below.]

Claim labels:

• [A] elementary-rigorous;
• [B] rigorous modulo an explicitly named theorem or primary source;
• [C] plausible/structural-unverified, including literature-search

completeness and cost extrapolations;

• [D] computational-only.

0. Mandatory live-page gate

I fetched the live page and its discussion thread through the Bright Data residential cloud browser. Direct datacenter curl was not used for this gate.

The rendered live state was:

• status OPEN;
• 0 claimed proofs for this problem;
• Interested in collaborating None;
• Currently working on this problem None;
• five comments;
• last page edit 05 March 2026;
• a formalised statement is linked;
• OEIS sequence A039669 is linked.

Thus the required stop/collision rule did not fire. [D: direct live-page observation.]

Verbatim current statement

Are there infinitely many \(n\) (or any \(n>105\)) such that \(n-2^k\) is prime for all \(1<2^k<n\)?

Everything mathematical listed on the live page

The page lists the only known values as

identifies them with A039669, and says Mientka and Weitzenkamp proved there are no others at most \(2^{44}\). [D for the finite published computation, reported here exactly as the page reports it.]

The page attributes to Vaughan the bound

for some \(c>0\), where \(E(N)\) counts qualifying \(n\le N\). [B]

It points to Guy's problem A19 and the Prime Puzzles discussion. It also records Erdős's stronger conjecture that the number of exponents \(1<2^k<n\) for which \(n-2^k\) is prime is \(o(\log n)\). [D as a faithful report of the page; the displayed assertion itself is conjectural and hence [C].]

All five displayed comments

The forum warns that comments are the users' responsibility and are not verified. In newest-first order:

1. Julian Bruns, 10 May 2026, says he checked

\(2^{120}<n<2^{128}\), says an OEIS comment covers below \(2^{120}\), and links his C/GMP code and logs. He reports that the last block took about an hour on an M5 MacBook. [D-unverified: a computational claim in a comment, not a proof claim.]

1. ebarschkis, 05 March 2026, points to the

Prime Puzzles page; the site says it was updated in response. [D: page observation.]

1. ebarschkis, 23 February 2026, observes that infinitely many such \(n\)

would imply infinitely many twin primes. This is correct because, for \(n>4\), both \(n-2\) and \(n-4\) must be prime. [A]

1. Woett, 23 February 2026, says that since there are “surely” only

finitely many, the problem need not be comparable in practice to twin primes. [C: opinion/heuristic.]

1. Dogmachine, 09 February 2026, says the usual heuristic suggests a

negative answer, while replacing “prime” by “squarefree” should give a positive answer. [C: heuristic.]

There was no hidden claimed-proof entry and no current-worker marker in the rendered discussion. [D: live-page observation.]

1. Primary-source literature audit

Erdős, 1950

The primary scan of P. Erdős, On integers of the form \(2^k+p\) and some related problems, Summa Brasil. Math. 2 (1950), 113--123, exists. On its page 115 Erdős says he cannot prove that not all the relevant differences are prime for all sufficiently large \(n\), notes that \(n=105\) works, records the exclusion through

and says 105 is likely the largest exception. [D for the prime-table computation; B for what the primary paper states.]

The same paper formulates \(f(n)\), proves \(f(n)\gg\log\log n\) infinitely often, and conjectures \(f(n)=o(\log n)\). [B]

Mientka--Weitzenkamp and a numerical discrepancy

The publisher record for W. E. Mientka and R. C. Weitzenkamp, On \(f\)-plentiful numbers80067-0), J. Combinatorial Theory 7 (1969), 374--377, DOI 10.1016/S0021-9800(69)80067-0, exists. The full publisher PDF was not available to my datacenter session, so I do not pretend to have audited its program directly. [D: bibliographic verification.]

There is a real secondary-primary discrepancy worth preserving:

• Uchiyama--Yorinaga quote Mientka--Weitzenkamp's endpoint as

\[ 18734724677955 =3\cdot5\cdot11^2\cdot13\cdot17\cdot19\cdot29^2\cdot37\cdot79 >2^{44}; \]

• Elsholtz's 2004 paper prints 187934724677955.

The standalone verifier recomputes the first factorisation. I did not resolve which longer decimal is the intended historical endpoint, and therefore use only the common, conservative consequence on the live page: exclusion through \(2^{44}\). [A for the product arithmetic; C for the unresolved bibliographic discrepancy; D for the historical computations.]

Uchiyama--Yorinaga, 1977

The primary scan of S. Uchiyama and M. Yorinaga, Notes on a conjecture of P. Erdős. I, Math. J. Okayama Univ. 19 (1976/77), 129--140, exists. It says their HITAC 20 computation found no solution in

It gives an explicit exclusion algorithm and reports that every tested value had a relevant difference divisible by a prime at most 179. The factorisation and comparison with \(2^{77}\) are recomputed by the verifier. [A for the arithmetic; D for the published finite computation.]

The paper proves the critical-prime proposition used below: if \(2\) is a primitive root modulo a prime \(q\), a qualifying \(n\) which is not divisible by \(q\) must satisfy \(n\le q+2^{q-1}\). The proof is the one-line residue argument reproduced in Section 2. [A; also B as a primary-source match.]

Vaughan, 1973, and Elsholtz, 2004

R. C. Vaughan, Some applications of Montgomery's sieve90059-0), J. Number Theory 5 (1973), 64--79, DOI 10.1016/0022-314X(73)90059-0, exists. The publisher abstract explicitly states this Erdős conjecture and says the paper estimates the number of such \(n\le N\). [D: primary publisher metadata.]

Christian Elsholtz, Upper bounds for prime \(k\)-tuples of size \(\log N\) and oscillations, Arch. Math. 82 (2004), 33--39, DOI 10.1007/s00013-003-4780-3, restates Vaughan's bound exactly in the form (0.1), cites the \(2^{77}\) Uchiyama--Yorinaga computation, and proves a comparable upper bound for general prime patterns of logarithmic size. [B]

Elsholtz also explains the order-of-2 connection, although the paper's prose uses the shortened condition \(2^{p-1}<n\). The exact elementary statement has an equality exception: if \(p\nmid n\), the divisible difference can equal the prime \(p\). A sufficient unconditional threshold is

as Uchiyama--Yorinaga state. (The known example \(n=7,p=3\) shows why the \(+p\) cannot simply be discarded in a literal finite statement.) Under a quantitative Artin conjecture, this order-of-2 method gives only a power-saving count \(E(N)\ll N^{\alpha+\varepsilon}\), not finiteness. [B modulo the quantitative Artin theorem cited there; A for the corrected divisibility implication.]

Current-search result

I searched exact variants of the statement, both historical decimal endpoints, the titles above, forward references to Vaughan, and 2025--2026 mentions of A039669. I found the primary sources above, the live comment, OEIS, and the Prime Puzzles discussion, but no primary source claiming a proof, counterexample, or verified computation beyond \(2^{128}\). This is an honest search miss, not a proof of bibliographic completeness or a priority claim. [C]

OEIS currently says “No other terms below \(2^{120}\)” in a 2011 user comment. Like the forum's \(2^{128}\) claim, I do not promote that comment to a theorem. [D-unverified.]

2. Elementary reduction behind the new computation

Write \(P(n)\) for the property on the live page.

Lemma 1: parity

If \(n>4\) and \(P(n)\), then \(n\) is odd. If \(n\) were even, \(n-2>2\) would be an even composite. [A]

In particular \(2^{128}\) itself fails. [A]

Lemma 2: primitive-root forcing in the target interval

Let \(p\) be an odd prime for which \(2\) is a primitive root modulo \(p\) and \(p-1\le128\). Suppose

and \(P(n)\). Then \(p\mid n\). [A]

Indeed, if \(p\nmid n\), the values

are all the nonzero residue classes. Thus some \(1\le k\le p-1\le128\) satisfies \(n\equiv2^k\pmod p\). But

so \(n-2^k\) is a positive proper multiple of \(p\), contrary to \(P(n)\).

\(\square\)

The verifier computes the multiplicative orders in two independent ways (direct cycling and factor reduction of \(p-1\)) and obtains exactly

Therefore \(M\mid n\) throughout the target interval above \(2^{128}+1000\). [D for the enumerated list, with every order independently rechecked; A for the implication.]

By Lemma 1, write

Lemma 3: exact residue exclusions for the multiplier

Let \(q\le1000\) be an odd prime not dividing \(M\). For each \(1\le k\le128\), the congruence

forbids one residue of \(x\bmod q\). Repeated powers may give the same residue; the verifier forms their exact set. [A]

If (2.3) holds in our interval, then \(q\mid n-2^k\) and

Thus \(n-2^k\) is composite. There is no equality exception. [A]

Solving (2.3) gives the two algebraically equivalent formulas

The verifier builds both sets and asserts equality prime by prime. [A for the identity; D for its exhaustive execution.]

There are 153 non-forced odd primes at most 1000. The strongest initial restrictions leave the following numbers of residues:

The ordering in (2.5) is by exact allowed fraction, not by \(q\). [D]

3. Exact interval and endpoint bookkeeping

The verifier separately covers every

by recording a pair \((k,q)\) with prime \(q\le997\) a proper divisor of \(n-2^k\). All 1000 witnesses are recomputed; their deterministic digest is

94c7eb01430f16806dfd50c4cfbe9e64a54fd5eb65d17b448699fd949f0fdb82

[D]

For \(n\ge2^{128}+1001\), Lemma 2 forces \(M\mid n\). The first eligible odd multiple has

The previous odd multiple of \(M\) is below \(2^{128}+1001\); this inequality is asserted by the verifier. [A for what the inequalities imply; D for the computed integers.]

The exhaustive range is

The next possible odd multiple of \(M\) is

Hence zero survivors in (3.2), together with the prefix witnesses and parity, proves the full integer interval (R). [A conditional only on the finite exhaustive result D.]

The arithmetic in (3.1)--(3.3), including both floor/ceiling boundary checks, is recomputed from scratch rather than read from a table. [D]

4. Implementation and repeat runs

The full standalone checker is erdos1142_wave6v_verify.py. It uses Python 3.12.3 and NumPy 2.4.4. NumPy is used only for exact unsigned-integer remainder and Boolean filtering. [D]

Its proof-critical covering loop is:

# M and the forbidden residue sets have already been independently audited.
for offset in range(0, multiplier_count, chunk_size):
    lo = x_first + offset
    length = min(chunk_size, multiplier_count - offset)
    survivors = np.arange(lo, lo + length, dtype=np.uint64)
    for stage, item in enumerate(restrictions, start=1):
        residues = survivors % np.uint64(item.p)
        survivors = survivors[item.allowed[residues]]
        if survivors.size == 0:
            digest.update(
                f"{lo}:{length}:{stage}:{item.p}\n".encode("ascii")
            )
            break
    if survivors.size:
        raise AssertionError(("survivors", lo, survivors[:10]))

The hardened checker additionally does all of the following:

1. generates primes at most 1000 by Eratosthenes and independently checks

every entry and non-entry by trial division; [D]

1. computes every \(\operatorname{ord}_p(2)\) both by cycling and by

factor-reducing \(p-1\); [D]

1. directly checks that the 128 powers cover every nonzero residue for every

forced prime; [D]

1. constructs (2.4) in two independent algebraic forms and compares the

resulting sets; [D]

1. independently scalar-checks the first 20,000 multiplier values; [D]
2. recomputes the known values through \(n=10,000\) by exact trial-division

primality, obtaining only \(4,7,15,21,45,75,105\); [D]

1. checks frozen SHA-256 values for both the 1000 boundary witnesses and the

1000 full chunks. [D]

Exact command

python3 runs/erdos1142_wave6v_verify.py

The first full run finished in 104.566 seconds. After the two digests were frozen as regression constants, a second full covering run finished in 104.795 seconds and matched them. I then added and separately ran the literature-factorisation preflight shown on the first line below; that additive check does not touch the covering loop or either frozen digest. The combined certificate-critical output was:

LITERATURE_ARITHMETIC UY_MW_QUOTE=18734724677955>2^44 UY=152246817378604933869885>2^77
FORCED primes=3,5,11,13,19,29,37,53,59,61,67,83,101,107 product=501298473603407557935 bits=69
PREFIX interval=[2^128+1,2^128+1000] values=1000 witness_sha256=94c7eb01430f16806dfd50c4cfbe9e64a54fd5eb65d17b448699fd949f0fdb82
RESTRICTIONS count=153 strongest=131:3/131 139:11/139 149:21/149 163:35/163 173:45/173 179:51/179 181:53/181 197:69/197 211:83/211 227:99/227 239:120/239 199:100/199
FULL_BLOCK x_first=339400960544462155 x_last=678801921088924309 x_count=339400960544462155
SCALAR_AUDIT x_values=20000 result=covered
MAIN n_first_multiple=340282366920938463842731497476562457785 x_first=339400960544462155 x_count=5000000000 next_possible_multiple=340282371933923199876807076826562457785 claimed_upper=340282371933923199876807076826562457784
CLEARED_BY 41:1 47:1 97:1 103:4 137:5 167:14 181:3 191:15 193:36 197:126 199:79 211:317 227:279 239:119
COVER_SHA256 c9a8324d2b62fad6e5df2aef08f47a18283ceab7593e1a1c9ebe5e3d49eb8fbe
VERIFIED_RANGE lower=340282366920938463463374607431768211456 upper=340282371933923199876807076826562457784 extension=5012984736413432469394794246328 survivors=0

The CLEARED_BY counts sum to 1000 chunks, each of five million \(x\)-values. No primality oracle is involved in the large computation: survivors=0 means every value received an explicit modular compositeness obstruction. [D, with the logical interpretation A.]

5. What this result does and does not establish

The interval (R) begins at exactly \(2^{128}\), so it is adjacent to the latest forum comment's strict interval ending at \(2^{128}\). It extends that reported endpoint by about \(5.013\times10^{30}\), or by a relative \(1.47318\times10^{-8}\) of \(2^{128}\). [A for the arithmetic; D for the finite exclusion.]

I did not independently rerun the comment's \(2^{120}\)-to-\(2^{128}\) search, and I do not use its logs to claim a theorem below \(2^{128}\). Therefore this report's self-contained new computation is the interval (R), not a self-contained proof that 105 is the only value all the way through its upper endpoint. [A: scope statement.]

Combining the published Uchiyama--Yorinaga computation through the integer in (1.1) with informal OEIS/forum computations would give a much longer continuous empirical range, but the latter two links remain unverified comments here. [D/C.]

6. Exact wall to a uniform solution

A finite set of sieve primes can never finish the problem

For any finite set \(S\) of odd primes and every multiple \(n\) of \(\prod_{p\in S}p\), one has \(n\equiv0\pmod p\) but \(2^k\not\equiv0\pmod p\) for each \(p\in S\). Consequently no difference \(n-2^k\) is divisible by a prime in \(S\). Thus no fixed finite modular covering of the type used here can exclude all \(n\). [A]

This is not merely a runtime issue; it is the precise logical reason a finite certificate cannot prove the global conjecture. The set of primes must grow with \(n\), and the remaining CRT classes must be controlled uniformly. [A]

The primitive-root product leaves a large multiplier

At exponent 128 the forced modulus \(M\) has 69 bits, whereas \(n\) has 129 bits in the full dyadic block. The complete block

contains exactly

eligible odd \(M\)-multipliers after the \(+1000\) prefix. This report checks five billion of them, a fraction

[A for the reduction; D for the counts.]

Under the Artin-density heuristic, primitive-root primes have density about \(0.3739\); their product up to exponent \(m\) grows too slowly relative to \(2^m\) to make the multiplier range disappear. This explains why adding only forced primitive-root primes does not turn the computation into a finite proof. [C: heuristic explanation, not used in the certificate.]

Named missing lemma

A solution would need a uniform result of the following strength:

For every sufficiently large odd \(n\), there is a \(k\le\lfloor\log_2(n-1)\rfloor\) and a prime \(q<n-2^k\) such that \(q\mid n-2^k\).

That assertion is exactly the desired eventual-compositeness conclusion restated with a factor witness, so it is not a hidden simplification. What is missing from current sieve machinery is a theorem that forces such a witness uniformly while the set of shifts itself grows like \(\log n\). Vaughan's density bound (0.1) still permits infinitely many exceptions. [A for the equivalence; B for Vaughan's limitation.]

Cost of brute continuation

At the measured vector-filter rate, scanning the rest of the entire \(2^{128}\)-to-\(2^{129}\) block linearly would take roughly 225 single-core years. [C: linear extrapolation from the exact count and measured run.]

The linked Bruns CRT/backtracking log for the preceding block records 53,616.74 user seconds, about 14.9 core-hours, and 5,393 wall seconds on 12 threads. Simple doubling suggests roughly 30 core-hours for the next full block, perhaps \(1\)--\(3\) USD at \(0.05\)--\(0.10\) USD per vCPU-hour, before independent reruns. This is only a hardware/algorithm estimate, not a verified bound, and I did not run it on this VM. [C]

The computation requested here stayed below two minutes per full single-process run and a few CPU-minutes total for the two full passes. [D]

PARTIAL: Exact modular covering proves there is no solution for \(2^{128}\le n\le340282371933923199876807076826562457784\); the uniform Erdős problem remains open.