← All problems

Erdős Problem #1113 — Sierpiński numbers with unbounded least prime divisors

46 years old · traced to

A Sierpiński number is a positive odd integer mm for which 2km+12^k m+1 is composite for every integer k≥0k\geq 0. A set PP of primes is a covering set for mm if

∀k≥0  ∃p∈P such that p∣(2km+1).\forall k\geq 0\;\exists p\in P\text{ such that }p\mid (2^k m+1).

The question is whether there exists a Sierpiński number mm for which no finite set of primes is a covering set. The k=0k=0 condition causes no discrepancy with the traditional definition using k≥1k\geq1: m=1m=1 fails the condition, and for any odd m>1m>1, m+1m+1 is composite. Erdős Problems #1113 Izotov, A Note on Sierpinski Numbers (1995)

For a Sierpiński number let qm(k)q_m(k) denote the least prime divisor of 2km+12^k m+1. The question is equivalently whether some such mm has unbounded least prime divisors:

no finite covering set exists for m⟺{qm(k):k≥0} is unbounded.\text{no finite covering set exists for }m \quad\Longleftrightarrow\quad \{q_m(k):k\geq0\}\text{ is unbounded}.

Indeed, a finite cover bounds all the qm(k)q_m(k) by its largest prime, while a bound on the qm(k)q_m(k) makes the finite set of all primes up to that bound a cover. Erdős Problems #1113

Background

Sierpiński’s 1960 construction established that infinitely many odd integers are Sierpiński numbers by using finite sets of primes to cover all exponents. The construction works for integers satisfying suitable congruence conditions and yields a positive-density set of examples. The underlying periodicity is that, for an odd prime pp dividing a term, 2k2^k modulo pp repeats periodically; thus divisibility by a fixed prime occurs in recurring exponent classes. The problem asks whether Sierpiński numbers can exist without any finite collection of such recurring divisors accounting for every exponent. Erdős Problems #1113 Sierpiński (1960)

Erdős and Graham posed the question in Old and New Problems and Results in Combinatorial Number Theory (1980); it was later formulated precisely as problem F13 in Guy’s collection. The historical motivation was whether some Sierpiński numbers arise in a way not explained by a covering system. Erdős and Graham believed such examples should exist. Erdős Problems #1113 Erdős and Graham (1980)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.