Erdős problem #1113 — wave8f
Date: 2026-07-28 (UTC)
Outcome
The problem remains open. I obtained two exact obstructions for the Izotov–Filaseta–Finch–Kozek candidate
\[ \ell=734110615000775,\qquad m=\ell^4 =290433036530614504024730081259407069229771426966923250390625. \]- [d] Cardinality certificate. Every finite prime covering set for this \(m\), if one exists, has at least 686 distinct primes. The certificate is an explicit set of 686 exponents \(u\leq 5000\) for which
\[ T_u=m2^{4u+2}+1=4\ell^4 16^u+1 \]
are pairwise coprime. The standalone checker performs all \(234955\) exact pairwise gcd computations.
- [d] Size/period certificate. Every such cover contains a prime
\[ p\geq 376843822247957 \]
whose divisibility class on the \(u\)-sequence has period
\[ \operatorname{ord}_p(16)\geq 94210955561989. \]
This follows from a complete, rigorously primality-certified factorization of \(T_{83}=m2^{334}+1\).
Neither finite certificate proves that no finite cover exists, and I make no such claim. I did not find the 686-term certificate in the sources searched, but I have not established literature novelty.
Claim labels used below:
- [a] elementary-rigorous;
- [b] rigorous modulo the explicitly named theorem/source;
- [c] plausible or structural but unverified;
- [d] computational-only, backed by the standalone exact checker.
Step 0: mandatory live-page audit
I fetched the rendered page, its LaTeX view, and its discussion thread through the Bright Data browser route on 2026-07-28.
Live-page facts:
- Status: OPEN.
- Claimed proofs: 0.
- “Currently working on this problem”: None.
- “Interested in collaborating”: None.
- Last page edit: 29 December 2025.
- There is one comment. Dogmachine suggested linking #276 because it is in the same vein; the page says that this was done. It contains no mathematical claim or worker marker.
Thus none of the mandatory stop conditions fired.
The exact mathematical content of the statement is:
\[ \begin{aligned} m\in 2\mathbb Z+1\text{ is Sierpiński} &\iff 2^k m+1\text{ is nonprime for every }k\geq0,\\ P\text{ is a prime cover for }m &\iff \forall k\geq0\ \exists p\in P:\ p\mid 2^k m+1. \end{aligned} \]The page's exact interrogative sentence is:
> Are there Sierpinski numbers with no finite covering set of primes?
This is the same mathematical statement as the live LaTeX source. The rendered body flattens the superscript in the later candidate; the LaTeX endpoint unambiguously gives \(734110615000775^4\).
Sources: live page, LaTeX view, discussion thread.
Results and comments listed on the live page
The following are page-listed background, not new claims of this report.
- Sierpiński proved there are infinitely many Sierpiński numbers by a finite covering construction; the resulting set has positive density.
- The smallest Sierpiński number is believed to be \(78557\), found by Selfridge.
- Erdős and Graham asked whether a covering system must be “responsible.” The page interprets this as the present finite-prime-cover question and says they expected the answer to be yes (such examples should exist), because the contrary would imply infinitely many Fermat primes.
- Izotov proved that the fourth powers in a specified congruence family are Sierpiński numbers. The page highlights \(\ell^4\) for \(\ell=734110615000775\) as a concrete candidate that appears to lack a finite cover.
- Filaseta, Finch, and Kozek conjectured that every Sierpiński number which is not a perfect power has a finite cover. They proved that, for every \(L\geq1\), some \(m\) makes \(m,m^2,\ldots,m^L\) simultaneously Sierpiński.
- The page links problems #203 and #276 as related covering-system questions.
Primary-source search and current state
I searched exact titles, the candidate base, “finite covering set,” “bounded smallest prime divisor,” and papers citing the 2008 work. The useful primary sources were:
1. Sierpiński (1960). W. Sierpiński, Sur un problème concernant les nombres \(k2^n+1\), Elemente der Mathematik 15 (1960), 73–74, DOI 10.5169/seals-20713. The bibliographic record and full scan exist.
2. Erdős–Graham (1980). P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, p. 27, author-hosted scan. I OCR-checked the scanned page. It asks whether a finite covering system must be responsible and says the answer is probably no; otherwise one would obtain infinitely many Fermat primes.
3. Izotov (1995). A. S. Izotov, A Note on Sierpinski Numbers, Fibonacci Quarterly 33 (1995), 206–207, journal PDF, DOI 10.1080/00150517.1995.12429134. Theorem 1 and its proof give the fourth-power construction: a six-prime partial cover handles \(n\not\equiv2\pmod4\), while the Sophie Germain identity handles \(n\equiv2\pmod4\).
4. Filaseta–Finch–Kozek (2008). M. Filaseta, C. Finch, and M. Kozek, On powers associated with Sierpiński numbers, Riesel numbers and Polignac's conjecture, J. Number Theory 128 (2008), 1916–1940, author PDF, DOI 10.1016/j.jnt.2008.02.004. Section 2 derives the displayed \(\ell\), gives numerical evidence at exponents \(14,118,334\), and explicitly says that proving the examples do not arise from a covering argument “seems out of reach.” Their Conjecture 3 is the non-perfect-power revision stated on the live page.
5. Järviniemi–Teräväinen (2023). O. Järviniemi and J. Teräväinen, Composite values of shifted exponentials, Advances in Mathematics 429 (2023), 109187, DOI 10.1016/j.aim.2023.109187, open PDF. Their Theorem 1.6, conditional on GRH and their Hypothesis 1.2, gives many distinct prime factors for almost all shifted exponentials. In Section 11 they explicitly observe that this does not rule out a bounded smallest prime factor, and they still identify unboundedness even for \(5\cdot2^n+1\) as unresolved.
I found no primary paper claiming a solution of the finite-cover question or of the Izotov candidate. This is a search result, not a proof of absence; the live page is still marked OPEN and has no claimed proof.
Exact reduction to the missing lemma
For a positive integer \(N>1\), write \(\operatorname{spf}(N)\) for its smallest prime factor.
Lemma 1: finite cover iff bounded smallest factor
For fixed odd \(m\), the following are equivalent:
1. \(m\) has a finite prime covering set.
2. \(\operatorname{spf}(m2^n+1)\) is bounded as \(n\geq0\) varies.
Proof [a]. If \(P\) is a finite cover, then
\[ \operatorname{spf}(m2^n+1)\leq\max P \]for every \(n\). Conversely, if all smallest factors are at most \(B\), the finite set of primes \(p\leq B\) which divide at least one term covers every term. \(\square\)
Lemma 2: every usable prime supplies one residue class
Set
\[ T_u=4\ell^4 16^u+1. \]If an odd prime \(p\) divides one \(T_a\), then \(p\nmid2\ell\), and
\[ p\mid T_u \quad\Longleftrightarrow\quad u\equiv a\pmod{\operatorname{ord}_p(16)}. \]Proof [a]. Since \(p\mid T_a\), neither \(2\) nor \(\ell\) is zero modulo \(p\). Dividing the congruences for \(T_u\) and \(T_a\) gives \(16^{u-a}\equiv1\pmod p\), which is equivalent to the stated order divisibility. \(\square\)
For the Izotov candidate, therefore, a proof that it has no finite cover is exactly a proof of either equivalent statement
\[ \sup_{u\geq0}\operatorname{spf}(T_u)=\infty, \]or
> no finite collection of the eligible classes
> \(u\equiv a_p\pmod{\operatorname{ord}_p(16)}\)
> covers all nonnegative integers.
This is the precise uniformity lemma still missing.
From-scratch proof that the candidate is Sierpiński
This section is independent of the unproved “no finite cover” expectation.
The checker verifies
\[ \ell\bmod(2,3,5,17,257,65537,641,6700417) =(1,2,0,13,256,1,640,3376382) \]and, after taking fourth powers,
\[ m\equiv1\pmod{3,17,257,65537,641}, \qquad m\equiv-1\pmod{6700417}. \]The following six cases cover every \(n\not\equiv2\pmod4\):
| Exponent class | Divisor of \(m2^n+1\) |
|---|---:|
| \(n\equiv1\pmod2\) | \(3\) |
| \(n\equiv4\pmod8\) | \(17\) |
| \(n\equiv8\pmod{16}\) | \(257\) |
| \(n\equiv16\pmod{32}\) | \(65537\) |
| \(n\equiv32\pmod{64}\) | \(641\) |
| \(n\equiv0\pmod{64}\) | \(6700417\) |
The checker tests all 48 relevant residues modulo 64 directly.
For \(n=4u+2\), put \(x=\ell2^u>1\). Then
\[ \begin{aligned} m2^n+1 &=4x^4+1\\ &=(2x^2-2x+1)(2x^2+2x+1), \end{aligned} \]and both factors are strictly between \(1\) and \(4x^4+1\). This also includes \(u=0\). Hence \(m\) is a Sierpiński number for every exponent \(n\geq0\). [a]
Computation 1: a 686-prime lower bound
Certificate
The verifier contains an explicit tuple \(U\) of 686 distinct integers in \([0,5000]\). It computes
\[ T_u=4\ell^4 16^u+1\qquad(u\in U) \]and checks
\[ \gcd(T_u,T_v)=1\qquad(u\ne v,\ u,v\in U). \]There are exactly
\[ \binom{686}{2}=234955 \]such gcd checks. Every \(T_u\) is composite by the displayed algebraic identity. If \(P\) covers the original sequence, it must contain a prime divisor of each \(T_u\). Pairwise coprimality means one prime cannot serve two selected terms, so
\[ |P|\geq686. \]This logical implication is elementary; the asserted gcd certificate is [d].
No minimality is claimed: 686 is a certified lower bound, not the maximum possible size of a pairwise-coprime subfamily.
How the certificate was found
1. For \(0\leq u\leq5000\), PARI/GP partial trial division of the two algebraic factors through primes \(<1000\) left 968 candidates. This was only a search heuristic.
2. I built the exact gcd graph on those 968 candidates. It had 2595 edges.
3. A deterministic “choose a current minimum-degree vertex and delete its neighbors” heuristic returned the 686 vertices embedded in the verifier.
4. The final checker does not trust the prefilter or graph-generation logic. It recomputes every claimed gcd directly from the embedded \(u\)-list.
The exact core of the verification is:
values = [4 * ELL**4 * 16**u + 1 for u in PAIRWISE_US]
for i, value_i in enumerate(values):
for j in range(i):
assert math.gcd(value_i, values[j]) == 1
Computation 2: exact obstruction at exponent 334
Take \(u=83\), so the original exponent is \(n=4u+2=334\). The two algebraic factors of \(T_{83}\) have the following complete factorization:
\[ \begin{aligned} 2x^2-2x+1 ={}& 1381185656143814897230397147713468069\\ &{}\cdot72992833727490048773126569085473176478384429, \\[3pt] 2x^2+2x+1 ={}& 376843822247957\\ &{}\cdot5954548581361657\\ &{}\cdot5758029433884712169221\\ &{}\cdot7802758403286434144655027169, \end{aligned} \]where \(x=\ell2^{83}\).
The factors were obtained as factor-discovery data and are not accepted on trust. The verifier:
1. multiplies them back to the two algebraic factors and to \(T_{83}\);
2. recursively factors every \(p-1\);
3. recursively proves the alleged prime factors of \(p-1\);
4. finds and checks a Lucas primality witness \(a\) satisfying
\[ a^{p-1}\equiv1\pmod p,\qquad \gcd(a^{(p-1)/q}-1,p)=1 \quad\text{for every prime }q\mid p-1; \]
5. computes each multiplicative order by exact division of \(p-1\).
Thus the primality verification is a rigorous Lucas-criterion certificate, not merely a probable-prime test. The resulting exact periods are:
| Prime \(p\mid T_{83}\) | \(\operatorname{ord}_p(16)\) |
|---:|---:|
| \(376843822247957\) | \(94210955561989\) |
| \(5954548581361657\) | \(744318572670207\) |
| \(5758029433884712169221\) | \(1439507358471178042305\) |
| \(7802758403286434144655027169\) | \(3434312677502831929865769\) |
| \(1381185656143814897230397147713468069\) | \(345296414035953724307599286928367017\) |
| \(72992833727490048773126569085473176478384429\) | \(18248208431872512193281642271368294119596107\) |
Any covering set must use one of these six primes on \(T_{83}\). Therefore its largest prime is at least \(376843822247957\), and the largest period among its \(u\)-classes is at least \(94210955561989\). [d]
Reproduction
Standalone verifier:
runs/erdos1113_wave8f_reverify.py
Run:
python3 runs/erdos1113_wave8f_reverify.py
Observed output:
PASS construction: ell^4 is Sierpiński (six-prime partial cover + identity)
cover primes: (3, 17, 257, 641, 65537, 6700417)
checked all 48 nonexceptional residues modulo 64
PASS cardinality certificate: 686 terms are pairwise coprime
exact gcd checks: 234955
consequence: every prime covering set has at least 686 members
PASS n=334 complete prime factorization and order certificate
least possible covering prime: 376843822247957
least possible covering period ord_p(16): 94210955561989
ALL CHECKS PASSED in 31.43s on Python 3.12.3
The script uses exact Python integers. SymPy is used to discover factorizations of \(p-1\); the script independently checks each product and each recursive Lucas congruence, so an erroneous factor-discovery result causes failure rather than a false primality certificate.
Why this does not close the problem
The factorization \(4x^4+1\) proves compositeness but says nothing uniform about how its prime divisors vary as \(x=\ell2^u\) varies. Every fixed prime divisor, when it occurs at all, recurs on one residue class modulo \(\operatorname{ord}_p(16)\). A very large finite collection of those classes could still cover all \(u\).
The exact missing lemma is unboundedness of
\[ \operatorname{spf}(4\ell^4 16^u+1). \]Neither many prime factors nor many pairwise-coprime initial terms proves this. In particular:
- the conditional Järviniemi–Teräväinen theorem produces many distinct factors for almost all exponents but explicitly does not exclude one bounded small factor on every term;
- an \(N\)-term pairwise-coprime certificate only proves \(|P|\geq N\), for finite \(N\);
- finite computation cannot supply the required uniform “for every finite prime set” step.
The measured exact-gcd rate was about \(7{,}000\) pairs/second on one core. A naive graph on all \(100001\) exponents through \(u=100000\) would require roughly \(5.0\times10^9\) gcds, about \(200\) core-hours at that rate, and would still yield only another finite lower bound. I did not run it.
The productive next mathematical target is therefore not a larger blind factorization table. It is a theorem preventing eligible classes \(a_p\bmod\operatorname{ord}_p(16)\) from finitely covering \(\mathbb N\), or equivalently a theorem forcing arbitrarily large least prime factors in this particular shifted exponential subsequence.
PARTIAL: The Izotov candidate is re-proved Sierpiński; any finite cover is certified to require at least 686 primes, including one at least 376843822247957 with period at least 94210955561989, but unbounded least prime factors remain unproved.