Sierpiński numbers without a finite covering set of primes: do they exist? (Erdős #1113)
Statement
A positive odd integer $m$ such that none of $2^km+1$ are prime for $k\geq 0$ is called a Sierpiński number. We say that a set of primes $P$ is a covering set for $m$ if every $2^km+1$ is divisible by some $p\in P$. Are there Sierpiński numbers with no finite covering set of primes? (Note that for a fixed odd prime $p$, the exponents $k$ with $p\mid 2^km+1$ form either the empty set or a single residue class modulo the multiplicative order of $2$ mod $p$, so a finite covering set is exactly a covering-system explanation of $m$'s compositeness.)
Acceptance. FULLY RESOLVES: (a) exhibit a specific integer $m$ with a complete proof that (i) $m$ is a Sierpiński number ($2^km+1$ composite for all $k\geq 0$) and (ii) no finite set of primes covers $\{2^km+1: k\geq 0\}$ — machine-checkable (Lean/Coq) strongly preferred, building on the existing formal-conjectures statement, else a full written proof; OR (b) prove that every Sierpiński number admits a finite covering set of primes (flagging that this implies infinitely many Fermat primes). A computation alone cannot close this, since (ii) quantifies over all finite prime sets. ADVANCES: a reproducible computation certifying that the Izotov–Filaseta–Finch–Kozek candidate $m=734110615000775^4$ admits no covering set whose induced covering of the exponents has period at most $B$, for an explicitly stated $B$ (code + exhaustiveness certificate, using the factor tables of $2^d-1$); a proof of the Filaseta–Finch–Kozek revised conjecture for a structured family, or of any theorem separating covering-driven from algebraically-driven Sierpiński numbers; or a new proven Sierpiński number together with a rigorous argument that its compositeness is not fully covering-driven. Deliver the proof file, or the search code plus certificates and the attained bound $B$.
Background
Posed by Erdős and Graham [ErGr80, p.27], and formulated precisely as problem F13 of Guy's collection [Gu04]; listed as open on erdosproblems.com/1113 (fetched 2026-07-13, status 'open', tagged 'number theory | covering systems'). Sierpiński [Si60] proved there are infinitely many Sierpiński numbers — a positive density set — by using covering systems: congruence conditions on $m$ force each $2^km+1$ to be divisible by one of a fixed finite set of primes. The smallest Sierpiński number is believed to be $78557$ (found by Selfridge); OEIS A076336 records the known provable Sierpiński numbers. This problem asks whether covering is the ONLY mechanism. Erdős and Graham expected the answer yes (such numbers exist), since the contrary would imply there are infinitely many Fermat primes. Concrete evidence: Izotov [Iz95] proved that $m=734110615000775^4$ is a Sierpiński number by combining a partial covering with an algebraic factorization for the exponents the covering misses (the fourth-power structure lets the Sophie Germain identity $4t^4+1=(2t^2+2t+1)(2t^2-2t+1)$ handle $k\equiv 2\pmod 4$); Filaseta, Finch, and Kozek [FFK08] elaborated this argument and suggest this $m$ has no finite covering set — though no proof of that is known. They also propose a revised conjecture (every Sierpiński number is either a perfect power or has a finite covering set) and prove that for every $l\geq 1$ there is an $m$ with $2^km^i+1$ composite for all $1\leq i\leq l$ and $k\geq 0$. A Lean formalisation of the statement exists in google-deepmind/formal-conjectures. Closely related: Erdős #203 (erdosproblems.com/203) asks the two-parameter analogue for $2^k3^\ell m+1$, and Erdős #276 asks another 'is a covering system always responsible' question; the venue also hosts covering-system problems Erdős #7 (all moduli odd) and #273 (moduli of the form $p-1$). Key finiteness lever for attackers: any prime with $\mathrm{ord}_p(2)=d$ divides $2^d-1$, so all primes that could cover exponents with period $d$ are found among the factors of $2^d-1$. The attacker's tools: exhaustively rule out covering sets of bounded exponent-period $B$ for the Izotov–FFK candidate (a finite, certifiable computation using factorizations of $2^d-1$, $d\leq B$), hunt for primes in the uncovered exponent classes, and develop the algebraic-factorization side into a rigorous non-covering proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1113 (T. F. Bloom) | website |
| REF-02 | OEIS A076336 — (provable) Sierpiński numbers: odd n with n·2^k+1 composite for all k ≥ 1 | website |
| REF-03 | Formalised statement of Erdős #1113 (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.