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
\[ 2^{128}\le n\le 340282371933923199876807076826562457784. \tag{R} \]The upper endpoint is
\[ 2^{128}+5012984736413432469394794246328. \]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 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 faithful report of the page; the displayed assertion itself is conjectural and hence [C].]** 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} 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.] 2. the site says it was updated in response. [D: page observation.] 3. would imply infinitely many twin primes. This is correct because, for \(n>4\), both \(n-2\) and \(n-4\) must be prime. [A] 4. finitely many, the problem need not be comparable in practice to twin primes. [C: opinion/heuristic.] 5. 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.] The primary scan of P. Erdős, [*On integers of the form \(2^k+p\) and some related problems*](https://www.renyi.hu/~p_erdos/1950-07.pdf), 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] The publisher record for W. E. Mientka and R. C. Weitzenkamp, On \(f\)-plentiful numbers80067-0), J. Combinatorial Theory 7 (1969), 374--377, DOI 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: \[
18734724677955
=3\cdot5\cdot11^2\cdot13\cdot17\cdot19\cdot29^2\cdot37\cdot79
>2^{44};
\] 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.]** The primary scan of S. Uchiyama and M. Yorinaga, [*Notes on a conjecture of P. Erdős. I*](https://www.math.okayama-u.ac.jp/mjou/mjou1-46/mjou_pdf/mjou_19/mjou_19_129.pdf), 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.] R. C. Vaughan, [*Some applications of Montgomery's sieve*](https://doi.org/10.1016/0022-314X(73)90059-0), J. Number Theory 5 (1973), 64--79, DOI 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*](https://www.math.tugraz.at/~elsholtz/WWW/papers/papers07ktuplelogN.pdf), Arch. Math. 82 (2004), 33--39, DOI (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} 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.]** 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.] Write \(P(n)\) for the property on the live page. 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] 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)\). 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 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] The verifier separately covers every \(n-2^k\). All 1000 witnesses are recomputed; their deterministic digest is [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 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] The full standalone checker is 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: 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] 2. computes every \(\operatorname{ord}_p(2)\) both by cycling and by factor-reducing \(p-1\); [D] 3. directly checks that the 128 powers cover every nonzero residue for every forced prime; [D] 4. constructs (2.4) in two independent algebraic forms and compares the resulting sets; [D] 5. independently scalar-checks the first 20,000 multiplier values; [D] 6. recomputes the known values through \(n=10,000\) by exact trial-division primality, obtaining only \(4,7,15,21,45,75,105\); [D] 7. checks frozen SHA-256 values for both the 1000 boundary witnesses and the 1000 full chunks. [D] 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: The No primality oracle is involved in the large computation: means every value received an explicit modular compositeness obstruction. [D, with the logical interpretation A.] 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.] 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] At exponent 128 the forced modulus \(M\) has 69 bits, whereas \(n\) has 129 bits in the full dyadic block. The complete block 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.] 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 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.]** 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.Everything mathematical listed on the live page
All five displayed comments
ebarschkis, 05 March 2026, points to theebarschkis, 23 February 2026, observes that infinitely many such \(n\)Woett, 23 February 2026, says that since there are “surely” onlyDogmachine, 09 February 2026, says the usual heuristic suggests a1. Primary-source literature audit
Erdős, 1950
Mientka--Weitzenkamp and a numerical discrepancy
10.1016/S0021-9800(69)80067-0, exists. The full publisher PDF was not
187934724677955.Uchiyama--Yorinaga, 1977
Vaughan, 1973, and Elsholtz, 2004
10.1016/0022-314X(73)90059-0, exists. The publisher abstract explicitly10.1007/s00013-003-4780-3, restates Vaughan's bound exactly in the formCurrent-search result
2. Elementary reduction behind the new computation
Lemma 1: parity
Lemma 2: primitive-root forcing in the target interval
Lemma 3: exact residue exclusions for the multiplier
3. Exact interval and endpoint bookkeeping
94c7eb01430f16806dfd50c4cfbe9e64a54fd5eb65d17b448699fd949f0fdb82
4. Implementation and repeat runs
erdos1142_wave6v_verify.py. It uses Python# 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]))
Exact command
python3 runs/erdos1142_wave6v_verify.py
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
CLEARED_BY counts sum to 1000 chunks, each of five million \(x\)-values.survivors=05. What this result does and does not establish
6. Exact wall to a uniform solution
A finite set of sieve primes can never finish the problem
The primitive-root product leaves a large multiplier
Named missing lemma
Cost of brute continuation