Erdős Problem #291

Erdős Problem 291

1) ROUND-2 OBJECTIVE

Path (C): correct and substantially strengthen the Round 1 understanding of the already-solved "$(a_n,L_n)>1$ infinitely often" half, while keeping the "$(a_n,L_n)=1$ infinitely often" half clearly separated as the unresolved part.

Why this is the right continuation of Round 1: Round 1 proved only the easy infinite family coming from the prime $3$. The real missing opportunity was to exploit the leading-digit criterion much more systematically.

2) Round-1 FOUNDATION USED

I use the following Round 1 result.

• $F1$ If $q_n:=\gcd(a_n,L_n)$ and $p\le n$ is prime, then \[ p\mid q_n \iff p\mid \operatorname{num}(H_k), \] where $k$ is the leading base-$p$ digit of $n$ and $H_k=1+\frac12+\cdots+\frac1k$.

3) NEW INSIGHT / TOOL (ROUND-2)

There are three new ingredients.

• $N1$ An exact set-theoretic description of \[ Q_p:=\{n\ge 1: p\mid q_n\} \] in terms of base-$p$ leading digits.
• $N2$ An exact counting formula for $Q_p\cap [1,p^b]$.
• $N3$ A new unconditional theorem: for any two distinct odd primes $p<q$, there are infinitely many $n$ with \[ pq\mid q_n. \] So the easy "$3\mid q_n$ infinitely often" family from Round 1 can be strengthened to simultaneous divisibility by any prescribed pair of odd primes.

4) ATTACK PLAN (ROUND-2)

The exact gap after Round 1 was that the leading-digit criterion was only used one prime at a time.

I therefore prove the following claims.

• $C1$ For each odd prime $p$, the set $Q_p$ is a union of explicit base-$p$ digit blocks.
• $C2$ For each odd prime $p$, the digit $p-1$ is always bad, so $Q_p$ is infinite.
• $C3$ For any two odd primes $p<q$, infinitely many of the $p$-blocks and $q$-blocks overlap.

Claim $C3$ is the real new theorem of this round.

5) WORK (ROUND-2)

Let $H_n=u_n/v_n$ be reduced, so that $q_n=L_n/v_n=\gcd(a_n,L_n)$. For an odd prime $p$, define \[ E_p:=\{m\in\{1,2,\dots,p-1\}: p\mid \operatorname{num}(H_m)\}, \qquad Q_p:=\{n\ge 1: p\mid q_n\}. \]

Proposition 291.1 (exact structure of $Q_p$).

For every odd prime $p$, \[ Q_p=\bigcup_{m\in E_p}\ \bigcup_{a\ge 1}[mp^a,(m+1)p^a-1]. \]

Proof.

Fix $n\ge 1$ and write its leading base-$p$ digit as $m$, so \[ n=mp^a+r, \qquad 1\le m\le p-1, \qquad 0\le r<p^a. \] Then by the Round 1 criterion $F1$, \[ p\mid q_n \iff p\mid \operatorname{num}(H_m) \iff m\in E_p. \] But the condition that the leading base-$p$ digit of $n$ equals $m$ is exactly \[ mp^a\le n<(m+1)p^a. \] Since $n$ is an integer, this is precisely \[ mp^a\le n\le (m+1)p^a-1. \] Taking the union over all possible $a\ge 1$ and all bad digits $m\in E_p$ gives the formula. $\square$

Corollary 291.2 (exact counting on powers of $p$).

For every integer $b\ge 1$, \[ |Q_p\cap[1,p^b]|=|E_p|\,\frac{p^b-p}{p-1}. \]

Proof.

Inside $[1,p^b]$, the blocks in Proposition 291.1 are exactly those with $a=1,2,\dots,b-1$, because the block $[mp^a,(m+1)p^a-1]$ lies below $p^b$ if and only if $a\le b-1$. For fixed $m$ and fixed $a$, the block length is exactly $p^a$. Hence \[ |Q_p\cap[1,p^b]| =|E_p|\sum_{a=1}^{b-1}p^a =|E_p|\,\frac{p^b-p}{p-1}. \] $\square$

Corollary 291.3 ($Q_p$ is infinite for every odd prime $p$).

For every odd prime $p$, one has $p-1\in E_p$. Hence $Q_p$ is infinite.

Proof.

Write \[ H_{p-1}=\sum_{j=1}^{p-1}\frac1j =\sum_{j=1}^{(p-1)/2}\left(\frac1j+\frac1{p-j}\right) =\sum_{j=1}^{(p-1)/2}\frac{p}{j(p-j)}. \] Each denominator $j(p-j)$ is prime to $p$, so the reduced numerator of $H_{p-1}$ is divisible by $p$. Thus $p-1\in E_p$. Now Proposition 291.1 shows that for every $a\ge 1$, \[ [(p-1)p^a,p^{a+1}-1]\subseteq Q_p, \] so $Q_p$ is infinite. $\square$

Theorem 291.4 (new unconditional two-prime theorem).

Let $p<q$ be distinct odd primes. Then there are infinitely many integers $n$ such that \[ pq\mid q_n=\gcd(a_n,L_n). \]

Proof.

By Corollary 291.3, for every $a\ge 1$ the interval \[ I_a:=[(p-1)p^a,p^{a+1}-1] \] is contained in $Q_p$, and for every $b\ge 1$ the interval \[ J_b:=[(q-1)q^b,q^{b+1}-1] \] is contained in $Q_q$. Thus it suffices to show that $I_a\cap J_b\neq\emptyset$ for infinitely many pairs $(a,b)$.

Set \[ \alpha:=\frac{\log p}{\log q}. \] This number is irrational: otherwise $\alpha=r/s\in\mathbb Q$ would imply \[ p^s=q^r, \] impossible for distinct primes. Hence the set of fractional parts $\{a\alpha\}$ is dense in $[0,1]$.

For each $a\ge 1$, let \[ b:=\lfloor a\alpha\rfloor, \qquad \Delta_a:=a\log p-b\log q=\log q\cdot \{a\alpha\}. \] Then $0\le \Delta_a<\log q$. Consider the open interval \[ \mathcal J:=\left(\log\frac{q-1}{p},\ \log\frac{q}{p-1}\right). \] This interval is nonempty because \[ \frac{q-1}{p}<\frac{q}{p-1} \iff (q-1)(p-1)<pq, \] and the last inequality is equivalent to $p+q-1>0$. Also $\mathcal J\subset(0,\log q)$ because $q-1>p$ (distinct odd primes differ by at least $2$) and $p-1>1$.

By density of $\{a\alpha\}$, there are infinitely many $a$ for which \[ \Delta_a\in\mathcal J. \] For such $a$ (with $b=\lfloor a\alpha\rfloor$) we have \[ \log\frac{q-1}{p}<a\log p-b\log q<\log\frac{q}{p-1}. \] Exponentiating gives \[ (q-1)q^b<p^{a+1}, \qquad (p-1)p^a<q^{b+1}. \] Since all quantities are integers, these strict inequalities are exactly what is needed for the integer intervals $I_a$ and $J_b$ to overlap. Hence for infinitely many pairs $(a,b)$ there exists some integer \[ n\in I_a\cap J_b. \] For such $n$, Proposition 291.1 yields simultaneously \[ p\mid q_n \qquad\text{and}\qquad q\mid q_n, \] so $pq\mid q_n$. Because there are infinitely many such pairs $(a,b)$, there are infinitely many such $n$. $\square$

Example.

Taking $(p,q)=(3,5)$, one explicit overlap occurs at $n=20$. Indeed $20$ begins with digit $2$ in base $3$ and digit $4$ in base $5$, so $15\mid q_{20}$. In fact \[ H_{20}=\frac{55835135}{15519504}, \qquad L_{20}=232792560, \qquad q_{20}=\frac{L_{20}}{15519504}=15. \]

Literature note.

Proposition 291.1 is exactly the block description behind Shiu's Theorem 2, and Shiu also proves the harmonic density formula \[ \delta(Q_p)=\frac{1}{\log p}\sum_{m\in E_p}\log\left(1+\frac1m\right). \] This is stronger than mere infinitude of $Q_p$, but it is not needed for Theorem 291.4.

6) ADVERSARIAL VERIFICATION

• Critical check on irrationality. The proof of Theorem 291.4 only uses the irrationality of $\log p/\log q$, which is unconditional. This is safe.
• Important correction of a tempting overclaim. Shiu's multivariate theorem for finitely many primes requires linear independence of \[ \frac{\log p_1}{\log p_i} \quad (1\le i\le k), \] which is equivalent to linear independence of the reciprocals $1/\log p_i$ over $\mathbb Q$. That hypothesis is not known in general. So one must not upgrade Theorem 291.4 from pairs of primes to arbitrary finite sets without adding an explicit hypothesis.
• Interval-overlap criterion. The inequalities \[ (q-1)q^b<p^{a+1}, \qquad (p-1)p^a<q^{b+1} \] are exactly the right integer conditions for $I_a\cap J_b\neq\emptyset$ because the right endpoints are $p^{a+1}-1$ and $q^{b+1}-1$.
• Dependence on Round 1. The only place Round 1 is used is Proposition 291.1, via the already-proved leading-digit criterion.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 makes genuinely new, rigorous progress:

• it gives an exact structural description of each one-prime divisibility set $Q_p$;
• it derives an exact counting formula for $Q_p\cap[1,p^b]$;
• it proves unconditionally that for any two distinct odd primes $p<q$, there are infinitely many $n$ with $pq\mid \gcd(a_n,L_n)$.

Thus the "$(a_n,L_n)>1$" half is now strengthened far beyond the easy base-$3$ family from Round 1. The remaining hard part is still the infinitude of $n$ with $\gcd(a_n,L_n)=1$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

• [Er291] T. F. Bloom, Erdős Problem #291, website entry, accessed 2026-03-07.
• [Sh24] P. Shiu, The denominators of harmonic numbers (Revised), arXiv:1607.02863v2, 2024.
• [WuYa22] B.-L. Wu and X.-H. Yan, On the denominators of harmonic numbers. IV, C. R. Math. Acad. Sci. Paris 360 $2022$, 53--57.

Erdős Problem #291: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

Put $L_n=\operatorname{lcm}(1,\ldots,n)$ and $a_n=L_nH_n$, where $H_n=\sum_{j\le n}1/j$. Are there infinitely many $n$ with $\gcd(a_n,L_n)=1$, as well as infinitely many with gcd greater than one?

All supplied versions considered: 291.tex. The source develops the already accessible greater-than-one side and correctly warns that multivariate logarithm independence is not automatic. I turn back to the difficult gcd-one side, rederive its exact finite test and run it with rational arithmetic.

2) WORK

Fix $p\le n$, let $e=\lfloor\log_p n\rfloor$ and $m=\lfloor n/p^e\rfloor$. Modulo $p$, only denominators divisible by $p^e$ survive in $a_n=\sum_{j\le n}L_n/j$. Consequently \[ a_n\equiv {L_n\over p^e}\sum_{u=1}^{m}u^{-1}\pmod p. \] The coefficient is invertible, since $v_p(L_n)=e$. Thus $p$ divides the gcd exactly when the harmonic sum of the leading base-$p$ digit $m$ is zero modulo $p$. For $p=2$, $m=1$ always, so two never divides the gcd. More generally primes with leading digit one cannot obstruct it.

The reproducible exact-rational loop in verification/batch_2_checks.py computes $H_n$ and $L_n$ incrementally for every $1\le n\le1000$. In lowest terms $H_n=u_n/v_n$, the gcd is $L_n/v_n$, so the test is simply $v_n=L_n$. It finds 145 successful indices, including every $n$ from 968 through 1000. This last run is finite and gives no extrapolation beyond the checked range.

3) ADVERSARIAL VERIFICATION

Primes greater than $n$ do not divide $L_n$ and are excluded. The formula is modulo $p$, not a complete higher-valuation formula. Testing larger and larger initial intervals does not furnish an infinite family, and successful runs may stop abruptly when a leading digit changes.

4) FINAL

UNRESOLVED. No structural mechanism guaranteeing infinitely many simultaneous good leading digits is proved. The greater-than-one half is known from the source; the gcd-one infinitude remains unresolved.

5) SOURCES CHECKED

No external theorem is used in the new argument. The supplied source was read in full; the saved Tao status snapshot is dated 2026-09-22.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 10%

OUTPUT

MODEL: Claude Opus 4.8 (agentic session in Claude Code; Lean 4 + Mathlib compile-verify loop) PROMPT STRATEGY: autonomous prover loop; accepted only on `lake env lean` exit 0 + clean `#print axioms`. Verification claims below are reported by the contributor; Lean proof artifacts are not included in this submission.

1) FORMAL RESTATEMENT Erdős Problem 291 concerns $a_n/L_n = \sum_{k\le n} 1/k$ in lowest-terms-free form: $L_n = \mathrm{lcm}(1,\dots,n)$ and $a_n = \sum_{k\le n} L_n/k$. Part (ii) (research solved; Steinerberger): the set $\{\,n : \gcd(a_n, L_n) > 1\,\}$ is infinite. Lean statement (defs a, L verbatim from the formal-conjectures corpus):

theorem erdos_291_parts_ii :
    True <-> {n : N | Nat.gcd (a n) (L n) > 1}.Infinite

2) LITERATURE/CONTEXT CHECK Steinerberger's observation (recorded in the corpus): any $n$ whose base-3 expansion begins with digit 2 has $3 \mid \gcd(a_n, L_n)$. The general criterion (a prime $p \le n$ divides $\gcd(a_n,L_n)$ iff $p$ divides the numerator of a truncated harmonic sum) is a separate, harder variant not attempted here.

3) ATTACK PLAN Explicit infinite family: $n = 2\cdot 3^k$ (base-3 leading digit 2). Show $3 \mid \gcd(a_n, L_n)$ for each member: $v_3(L_n) = k$ suffices to make every summand $L_n/j$ except the critical block divisible by 3, and the critical block contributes a multiple of 3. Infinitude via injectivity of $k \mapsto 2\cdot3^k$ (Set.infinite_of_injective_forall_mem).

4) WORK Kernel-verified chain: (i) $v_3$ lower bound on $L_n$ for $n = 2\cdot3^{k+1}$; (ii) $3 \mid a_n$ and $3 \mid L_n$ for the family, hence $1 < \gcd(a_n, L_n)$; (iii) injectivity of the family map; (iv) assembly:

theorem infinite_gcd_gt_one :
    {n : N | 1 < Nat.gcd (a n) (L n)}.Infinite

Local defs sanity-checked against the corpus's own test evaluations (L 1..4 = 1,2,6,12 and a 1..4 = 1,3,11,25 by decide).

5) VERIFICATION `lake env lean` exit 0, 0 errors, 0 sorry (lean4 v4.32.0-rc1 + Mathlib). `#print axioms` = [propext, Classical.choice, Quot.sound]. Tracked pipeline episode e2320b06 (kernel_verified).

6) FINAL STATUS: SOLVED (the research-solved part (ii); known observation of Steinerberger, now with a machine-checked proof). The other parts/variants of Problem 291 are untouched. Subject to expert review; the kernel check is the verification story.