Skip to content

Erdős Problem #1143

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, primes.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Choose finitely many primes \(p_1<\cdots<p_u\). No matter where we look, how many multiples of at least one selected prime must occur in every block of \(k\) consecutive positive integers?

Erdős Problem #1143 defines the sharp guaranteed count

\[ F_k(p_1,\ldots,p_u) =\min_{s\ge1}\sum_{j=0}^{k-1} {\bf1}\{\text{some }p_i\mid s+j\}. \]

The problem asks for estimates, particularly when

\[ k=\alpha p_u,\qquad \alpha>2. \]

The minimum over all starting positions distinguishes it from merely computing the expected proportion of multiples.

A small example

For the selected primes \(\{2,3,5\}\), the divisibility pattern repeats every

\[ \mathrm{lcm}(2,3,5)=30 \]

integers. Consequently, checking the 30 possible starting residues gives exact answers for any fixed \(k\).

The arithmetic fixture finds:

Interval length \(k\) Guaranteed minimum \(F_k(2,3,5)\)
1 0
5 3
10 6
16 11

The case \(k=16\) has \(k>3p_u=15\). Thus even a tiny example enters a parameter range where the general problem is difficult.

What is known

The maintained catalogue reports that Erdős and Selfridge obtained an “exact bound” when \(2<\alpha<3\), based on Vardi (1999).

However, the catalogue's editor explicitly states that no reference or corresponding paper has been found. That makes this a source-fidelity obligation, not a verified mathematical theorem whose formula can be filled in by assumption.

For \(\alpha>3\), the source reports that much remains unknown. The problem is connected to covering systems, reduced residue patterns and minimum counts across shifted intervals.

GCL's current state

Authenticated source audit #2414 independently proves the finite periodic reduction and computes the four sharp counts.

The unsourced Erdős–Selfridge claim has not been promoted into an accepted theorem statement.

What remains

Find Vardi's original citation chain and any actual Erdős–Selfridge proof. Develop a verified periodic or Chinese-remainder dynamic program for wider prime sets, while retaining the distinction between exact finite computations and an unknown uniform asymptotic.

Sources and claim boundaries

Erdős #1143; Vardi (1999), Problem 1.8; related Problem #970; GCL source return. The finite 30-residue minima are independently exact. The general problem remains open, and the quoted historical exact bound lacks a located primary source. Unaccepted draft.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2414 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction