Erdős Problem #389
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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.
The question in plain language
Erdős Problem 389 asks whether every positive integer \(n\) has a positive integer \(k\) for which the product of \(k\) consecutive integers beginning at \(n\) divides the next block of \(k\) consecutive integers:
The divisor and dividend have the same number of factors, but the second block is shifted to the right. The question is not whether one can find a \(k\) for a particular small \(n\); it asks for a witness for every \(n\), with no proposed bound on how large that witness may be. Divisibility here means that the quotient of the two integer products is an integer.
There is a small indexing wrinkle. The 1980 source uses products beginning at \(n+1\) and ending at \(n+k\), whereas the maintained page and the formal statement use products beginning at \(n\). Replacing the source variable by \(n-1\) aligns the formulas. The live version also includes \(n=1\), where \(k=1\) is immediate, so this shift does not change the universal question.
A small example
For \(n=2\) and \(k=5\), exact integer arithmetic gives
and
Thus \((n,k)=(2,5)\) is a verified witness in the maintained indexing. The older source's example \((n,k)=(2,4)\) is the same calculation after the shift: it checks \(3\cdot4\cdot5\cdot6\mid7\cdot8\cdot9\cdot10\), with quotient \(14\), and therefore corresponds to \(n=3\) on the live page.
An additional finite check is useful for scale. Direct products with arbitrary-precision integers give remainder zero for \(n=4,k=207\) and no zero remainder for any \(1\leq k<207\). This agrees with the formal variant recording \(207\) as the least witness for \(n=4\). Neither calculation says anything about an arbitrary later \(n\): a finite search can confirm witnesses, but cannot establish the universal quantifier or prove that a search found every possible witness unless its search range is explicitly exhaustive for the stated target.
What is known
The primary historical reference is Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 75. There the question is attributed to Erdős and Straus, and the authors record the shifted product formula, the small example, and the observation that no example was then known for source parameters \(n\geq10\). That last observation is historical, not a current status statement.
Ulas and Schinzel's 2013 paper, “A note on Erdős–Straus and Erdős–Graham divisibility problems” (International Journal of Number Theory 9 (2013), 583–599), studies this exact problem. It rewrites the source-indexed divisibility as
because both consecutive products contain a factor of \(k!\). Their Theorem 2.1 gives a prime-by-prime test using base \(p\) digit sums: for each prime dividing the first block, the relevant expression \(2s_p(k+n)-s_p(2k+n)-s_p(n)\) must be nonnegative. This is a useful computational interface, not a proof that every \(n\) has a witness.
The same paper proves infinitely many witnesses for its source-indexed \(n=1\), and transfers witnesses from that case to source-indexed \(n=2\). It reports computed least witnesses through \(n=16\), and gives values for \(n=17,18,19,20\) marked with asterisks because those values were inferred through a conjectural connection rather than fully checked as minima. Its Conjecture 2.10 is precisely the belief that every source-indexed \(n\) has a witness. These results are substantial finite and structural evidence, but they leave the assertion for all values of \(n\) open.
GCL's current state
The frozen catalogue evidence is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, entry number: "389", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. At that revision the informal and overall statuses are open, both dated 2025-08-31; formal status is unformalized, while statement-formalized metadata is yes.
The maintained Erdős Problems entry, accessed 2026-10-13, still labels the problem open and warns that a finite computation cannot resolve it. It displays the shifted-to-live statement, examples, and OEIS sequence A375071, which records computed minimal witnesses. This live page is useful status context but does not replace the primary source or the frozen catalogue lock.
The pinned formal provider is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/389.lean, blob 1f67d71e18636f00b4b7a370d0a44203904d8d41. Its main declaration has the universal statement with answer(sorry), so the file records the conjecture and its interface, not a completed proof. A separate IsLeast variant states the \(n=4\) result with \(207\) and contains a finite proof script; that local theorem must not be promoted into a solution of Problem 389.
What remains
A bounded successor task should first freeze the normalization: use the live statement, or explicitly use the source-indexed variable and document the shift. Its input can be one selected \(n\) and a finite interval \(1\leq k\leq K\). The target is an exact witness or an exact certificate that the interval contains none. A suitable method is the Ulas–Schinzel digit-sum criterion, independently cross-checked for any reported witness by direct arbitrary-precision products. Acceptance requires the stated products to have zero remainder and the tested range to be reproducible; falsification is either a nonzero remainder for the proposed witness or a missing witness in a claimed exhaustive interval. Stop when the chosen interval is exhausted, a source ambiguity reappears, or the arithmetic and criterion disagree. This gives useful evidence without pretending that finite coverage proves the universal claim.
Sources and claim boundaries
The original issue supplies the assignment and frozen hashes. The primary statement is in the 1980 book scan, p. 75; the relevant later paper is Ulas and Schinzel, DOI 10.1142/S1793042112501497, with its readable full-text preview. The pinned catalogue blob and formal file preserve the exact machine-facing inputs.
The article distinguishes the external theorem and computations, unverified reports or conjectural extrapolations, finite arithmetic checks, and a Lean statement containing sorry. It supplies no GCL mathematical certification. V2 ledger state alone decides accepted coverage. Original SOURCE RESULT/1 citation: authenticated original RESULT/1.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1659 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.