Summatory growth of $t_k(n)$, the least start making $n$ divide a run of $k$ consecutive integers (Erdős #394)
Statement
For integers $k\geq 2$ and $n\geq 1$, let $t_k(n)$ be the least positive integer $m$ such that $n$ divides the product of the $k$ consecutive integers starting at $m$: $$t_k(n)=\min\{m\geq 1 : n\mid m(m+1)(m+2)\cdots (m+k-1)\}.$$ Two questions are asked. (1) Is $$\sum_{n\leq x}t_2(n)\ll \frac{x^2}{(\log x)^c}$$ for some constant $c>0$? (2) Is it true that for every $k\geq 2$, $$\sum_{n\leq x}t_{k+1}(n)=o\!\left(\sum_{n\leq x}t_k(n)\right)?$$
Acceptance. FULLY RESOLVES: a complete proof (written in full, or machine-checkable) of statement (1) — that $\sum_{n\leq x}t_2(n)\ll x^2/(\log x)^c$ for some $c>0$, with an explicit admissible $c$ — and/or a complete proof or disproof of statement (2), the $o(\cdot)$ decay for all $k\geq 2$. ADVANCES: (a) an unconditional improvement of the best-known upper bound on $\sum_{n\leq x}t_2(n)$ that is asymptotically smaller than the Erdős–Hall bound $\frac{\log\log\log x}{\log\log x}x^2$ stated in the background, with full proof; (b) a proof of statement (2) for a single specific value of $k$; (c) resolving the factorial sub-questions — the order of $t_{n-3}(n!)$, or the infinitely-often claim $t_k(n!)<t_{k-1}(n!)-1$; (d) a large-scale computation of $\sum_{n\leq x}t_2(n)$ and $\sum_{n\leq x}t_k(n)$ (extending A344005) that rigorously brackets the constant/exponent and gives quantitative evidence on the ratio, delivered with reproducible code. Deliver the proof file, or the computation plus certificate.
Background
Due to Erdős and recorded in Erdős–Hall [ErHa78, p.16] and Erdős–Graham [ErGr80, p.76]; listed as open on erdosproblems.com/394 (fetched 2026-07-13, status 'open', tagged 'number theory'), formalised in the google-deepmind/formal-conjectures Lean repository, with related OEIS sequence A344005. History and frontier: Erdős conjectured $\sum_{n\leq x}t_2(n)=o(x^2)$, and Erdős and Hall [ErHa78] proved the stronger bound $\sum_{n\leq x}t_2(n)\ll \frac{\log\log\log x}{\log\log x}x^2$, conjecturing the true size to be $o\big(x^2/(\log x)^c\big)$ for every $c<\log 2$. A matching lower bound $\sum_{n\leq x}t_2(n)\gg x^2/\log x$ is immediate because $t_2(p)=p-1$ for every prime $p$. For the factorial argument, Erdős and Hall observed $t_{n-1}(n!)=2$ and $t_{n-2}(n!)\ll n$ (best possible, as $n=2^r$ shows), asked about the order of $t_{n-3}(n!)$, and asked whether $t_k(n!)<t_{k-1}(n!)-1$ holds for all $1\leq k<n$ for infinitely many $n$ (they verified this, with Selfridge, for $n=10$). No cash prize is attached. The attacker's tool: the tractable side is directly computing $t_k(n)$ — a short factorization/CRT search per $n$ — to tabulate the summatory functions and test the ratio in (2) empirically; the frontier itself is analytic, requiring sieve/mean-value estimates to improve the Erdős–Hall upper bound and a comparison argument for $\sum t_{k+1}$ versus $\sum t_k$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #394 (T. F. Bloom) | website |
| REF-02 | OEIS A344005 — sequence related to t_k(n), least m with n dividing m(m+1)...(m+k-1) | website |
| REF-03 | Formalised statement of Erdős #394 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.