Erdős Problem #291
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, unit fractions.
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.
Editorial authority: Publication status comes exclusively from the protected V2 ledger. This explanation does not constitute mathematical certification.
The question in plain language
For a positive integer \(n\), form the harmonic sum
Let \(L_n=\mathrm{lcm}(1,2,\ldots,n)\), the smallest positive integer divisible by every number from \(1\) through \(n\). Since each denominator divides \(L_n\), there is an integer \(a_n\) with \(H_n=a_n/L_n\). Erdős and Graham ask whether both of the following events happen for infinitely many values of \(n\):
Here “infinitely many” means that no matter how far out one searches, another such \(n\) exists. It is not a claim about a large but finite computation.
There is a useful denominator reformulation. Write \(H_n=c_n/d_n\) in lowest terms, so \(\gcd(c_n,d_n)=1\) and \(d_n>0\). Then \(d_n\) divides \(L_n\), \(a_n=c_nL_n/d_n\), and therefore
Thus the first half asks whether \(d_n=L_n\) infinitely often: the reduced harmonic denominator retains every prime power present in the least common multiple. The second half asks whether \(d_n<L_n\) infinitely often.
The original source is not a modern web page but Erdős and Ronald L. Graham, Old and New Problems and Results in Combinatorial Number Theory, L’Enseignement Mathématique Monographie 28 (1980), p. 34. The book’s wording uses \(a/L_n\) and asks for the two gcd behaviours; the later catalogue number “291” is an indexing label, not wording from that page.
A small example
At \(n=2\),
At \(n=6\),
These examples show both behaviours at small indices, but they do not address infinitude. I independently checked the arithmetic with exact rational numbers in Python, not floating-point approximations:
from fractions import Fraction
from math import gcd, lcm
def values(n):
h = sum((Fraction(1, k) for k in range(1, n + 1)), Fraction(0))
L = 1
for k in range(1, n + 1):
L = lcm(L, k)
a = h.numerator * (L // h.denominator)
return h, L, a, gcd(a, L)
for n in (2, 6):
print(n, values(n))
The exact output was (2, Fraction(3, 2), 2, 3, 1) and (6, Fraction(49, 20), 60, 147, 3). The same calculation verified the unconditional pattern used below for all \(n\) in the first five intervals \(6\le n<9\), \(18\le n<27\), \(54\le n<81\), \(162\le n<243\), and \(486\le n<729\).
What is known
The second half has an elementary proof. Fix \(j\ge1\) and take
The largest power of \(3\) not exceeding \(n\) is \(3^j\), and the only denominators among \(1,\ldots,n\) with exactly this power of \(3\) are \(3^j\) and \(2\cdot3^j\). After multiplying \(H_n\) by \(L_n\), every term whose denominator has a smaller power of \(3\) vanishes modulo \(3\). The two remaining contributions are proportional modulo \(3\) to
Consequently \(3\mid a_n\). Since \(n\ge6\), also \(3\mid L_n\), so \(\gcd(a_n,L_n)>1\). The displayed intervals are disjoint and contain arbitrarily large integers; hence the second event occurs infinitely often, unconditionally.
The first event is different. Peter Shiu’s revised paper describes \(d_n=L_n\) infinitely often as a conjecture, and does not prove it. Bing-Ling Wu and Xiao-Hui Yan prove a nearby conditional result: their Theorem 2 states that the set of \(n\) with \(d_n<L_n\) has upper asymptotic density \(1\), assuming that \(1/\log p\) is linearly independent over \(\mathbb{Q}\) for every finite set of distinct primes. This is a conditional strengthening of the already-known second half, not a proof that \(d_n=L_n\) infinitely often. In particular, neither paper closes the original two-part question.
GCL's current state
The authenticated source audit on original MATH-PROGRAMME issue #1561 returned exact RESULT/1 for ERDOS-CATALOGUE-0291-S01. Its exact disposition is SOURCE_LOCK_READY, not PARTIAL and not STATUS_CONFLICT; the issue itself remains open. The return records the original p. 34 source, the \(p=3\) argument, the conditional Wu–Yan result, and the limitation that the first half remains unresolved.
The pinned catalogue record is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry Git blob 4e60263a80af6207aca494d2e1388e44fa372889, with extracted-entry SHA-256 32ce961a5a39f3113369b946c69df2ca51f45a476dc1edf70dd56fa64fe43996. At that revision the whole-problem status is open, the informal update is dated 2025-08-31, formal_status is unformalized, and statement metadata is marked formalized: yes. Those fields distinguish a formalized statement from an accepted formal solution.
The pinned FormalConjectures/ErdosProblems/291.lean snapshot likewise contains statement and result interfaces with sorry; its presence is not a proof. The source audit also reports an external JSP package claiming a Lean build of the second half, but labels it UNREPLAYED. An external claimed Lean proof, an author manuscript, or a successful CI/build report is evidence to inspect, not GCL mathematical certification. No GCL certification of Problem 291 is asserted here.
What remains
The central unresolved target is the first event: prove that \(d_n=L_n\) for infinitely many \(n\), or find a mathematically sound obstruction showing that this cannot happen. The elementary \(p=3\) argument does not help with that target, because it deliberately produces common divisibility.
The source audit records a useful finite interface. For each prime \(p\le n\), let \(q=p^e\) be the largest power of \(p\) with \(q\le n\), and let \(k=\lfloor n/q\rfloor\). Then the divisibility of \(a_n\) by \(p\) can be tested through the numerator of the shorter harmonic sum \(H_k\). This reduces a prime-by-prime finite computation, but it does not establish an infinite set of indices with no such prime divisor. The audit also notes a boundary exception: the informal phrase “leading digit \(p-1\)” applies to odd primes, not to \(p=2\).
A bounded successor task is therefore to compute exact \(H_n\), \(L_n\), \(a_n\), and their gcd for \(1\le n\le N\) by two independent integer-arithmetic paths, while checking the prime-prefix criterion for every \(p\le n\). Agreement can expose implementation or statement errors and produce a reproducible finite certificate. It cannot be promoted into a proof of infinitude, a resolution of the first half, or GCL certification.
Sources and claim boundaries
- Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 34 — original two-part question. The scan used by the source audit has SHA-256
0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. - Wu and Yan, “On the denominators of harmonic numbers. IV,” Comptes Rendus Mathématique 360 (2022), 53–57, DOI 10.5802/crmath.282 — Theorem 2 on p. 54 and proof on pp. 55–57; conditional on their Conjecture 1.
- Shiu, “The denominators of harmonic numbers,” arXiv:1607.02863v2, revised 30 July 2024, DOI 10.48550/arXiv.1607.02863 — treats \(d_n=L_n\) infinitely often as a conjecture; the source-audit PDF hash is
085037c856ff113828b366b37bd5c6a5a31c5016c853e6df61b4d54b4b7e7ab3. - Original issue #1561 and its exact authenticated
RESULT/1— source-audit evidence with dispositionSOURCE_LOCK_READY, not proof certification. - Pinned catalogue entry and pinned formal statement — registry and formalization snapshots, not authority for a solved status. The formal file has commit
85f863718beeec7b58a3a1926ee92e3472bc2020, blob0af4e827da2d514b49ca54067023893955c0d1c0, and SHA-256f2cbf68a5592d5ba6f2e265fa9e53743b709e510cf02638142134534b004e648.
This is a source-qualified explanation. Its source links, exact arithmetic, and self-review do not constitute editorial admission, publication, independent mathematical review, or GCL certification. Any later admission must bind the exact manuscript bytes to the protected editorial process and separately preserve the open status of the unresolved first half.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1561 — 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.