Erdős Problem #394
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 394 studies how early a block of consecutive integers must become divisible by a given positive integer. For positive integers \(k\) and \(n\), define \(t_k(n)\) to be the least positive \(m\) for which \(n\) divides
The first question asks whether there is a fixed constant \(c>0\) such that, as \(x\) grows, the total
is at most a constant multiple of \(x^2/(\log x)^c\). In other words, does the average contribution of the two-term waiting time \(t_2(n)\) have a genuine power saving over the natural quadratic scale?
The second question compares blocks of different lengths. For every fixed integer \(k\ge2\), is the sum of waiting times for blocks of length \(k+1\) negligible compared with the corresponding sum for blocks of length \(k\)?
Here \(x\) tends to infinity, and the \(o\) notation means that the ratio tends to zero. These are asymptotic assertions about all sufficiently large inputs, not claims that can be settled by checking a large finite table.
A small example
Take \(n=12\). For two consecutive factors, \(3\cdot4=12\), while \(1\cdot2\), \(2\cdot3\), and no earlier positive start is divisible by \(12\). Thus \(t_2(12)=3\). For three factors, \(2\cdot3\cdot4=24\), so \(t_3(12)=2\).
The following finite exact-arithmetic calculation independently checks these values, the first ten values of each sequence, and the prime identity used for a lower bound.
from math import prod
def t(k, n):
m = 1
while prod(m + i for i in range(k)) % n:
m += 1
return m
assert t(2, 12) == 3
assert t(3, 12) == 2
assert [t(2, n) for n in range(1, 11)] == [1, 1, 2, 3, 4, 2, 6, 7, 8, 4]
assert [t(3, n) for n in range(1, 11)] == [1, 1, 1, 2, 3, 1, 5, 2, 7, 3]
assert all(t(2, p) == p - 1 for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
The resulting finite sums are \(\sum_{n\le10}t_2(n)=38\) and \(\sum_{n\le10}t_3(n)=26\). This verifies definitions and small instances only. It neither estimates the limit ratio in the second question nor proves any asymptotic bound. For a prime \(p\), the last assertion follows because among two consecutive integers a multiple of \(p\) first appears at \(p-1\); this explains why primes force a substantial lower contribution.
What is known
The primary source is P. Erdős and R. R. Hall, “On some unconventional problems on the divisors of integers,” Journal of the Australian Mathematical Society 25 (1978), 479–485. On printed page 481 they define the same minimum \(t_k(n)\) and discuss its restriction to factorials. On printed page 482, their Theorem 3 proves the upper bound
That is a real saving relative to \(x^2\), but it is much weaker than a fixed power of \(\log x\). On that page they conjecture that a bound with \((\log x)^{-c}\) should hold, and specifically suggest every fixed \(c<\log 2\). The same page records the adjacent-length asymptotic question and says that even its first nontrivial case had not been proved there.
The maintained Erdős Problems entry currently labels Problem 394 open and warns that its status reflects the site owner’s current belief rather than an exhaustive literature certificate. It repeats the Erdős–Hall estimate, the logarithmic-saving conjecture, the prime lower bound, and the factorial side questions. The frozen catalogue packet records the same informal and general status as open, with last update 2025-10-28. No later primary source was found in this bounded inquiry that changes either main question’s status.
GCL's current state
Issue #1664 is the source-audit assignment for this article. At the time of inspection it was AVAILABLE, carried the direct-editorial, cooperative, and source-audit labels, and had no comments, reservations, or existing RESULT/1. The protected triage class supplied by the issue is PROTECTED_READY_BACKLOG; it is not a mathematical verdict.
The catalogue evidence is pinned to teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, whose data/problems.yaml blob is 4e60263a80af6207aca494d2e1388e44fa372889. It says open, unformalized, with statement-formalized metadata marked yes. The exact Formal Conjectures file is pinned to commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 4ffdfffb4ea1213394ed6f3e98fa5a76d016398c. It contains the two main statements and several variants, but every theorem body is by sorry; this is formal statement coverage, not a replayed proof or certification.
What remains
The smallest safe next step is a bounded normalization-and-lemma package. Its input should be the pinned Erdős–Hall PDF, the exact catalogue entry, and the exact Lean file. It should produce a checked correspondence between the source’s positive-integer minimum and the Lean definition, followed by an elementary theorem that \(t_2(p)=p-1\) for prime \(p\), with an explicit finite test such as the calculation above. A useful second target is to formalize the finite identity for the first ten values without claiming an asymptotic result.
Acceptance should require matching quantifiers, the same summation domain, a proof or fully inspectable derivation of the prime lemma, and recorded exact outputs for selected inputs. Falsification is a domain mismatch, an earlier admissible start, or a discrepancy between the source and Lean definitions. The task should stop when the correspondence and finite lemma are settled, or immediately if the primary statement cannot be read unambiguously. It must not be presented as progress toward proving the logarithmic saving or the adjacent-length limit.
Sources and claim boundaries
The primary theorem and page references come from the 1978 Erdős–Hall paper; the inspected PDF had SHA-256 ee5aa5c33b6767141699a54d9ea31016b617a2d9e001a999b6ebb4cc7464cb86. The maintained status and editorial history are at Erdős Problems #394, last edited there on 2025-10-28. The catalogue and formal hashes are given above. Erdős and Graham, Old and new problems and results in combinatorial number theory, cited by the maintained entry and formal file, is supporting historical context; the 1978 paper is the primary source used for the theorem and question wording here.
The original issue’s source-result citation is authenticated original RESULT/1: no such comment existed during this audit, so no future URL or result was invented. The open labels, formal sorrys, finite calculations, and external theorems are kept distinct. V2 ledger state alone decides accepted coverage; this article supplies documentary context and source boundaries, not mathematical certification, publication authority, or a claim that either open question has been solved.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1664 — 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.