Problem 389. A divisibility problem for two consecutive blocks
Formal restatement
For each integer $n\ge 1$, does there exist an integer $k\ge 1$ such that
\begin{equation}
\label{wsref-0-65-71-3a-50-33-38-39-2d-6d-61-69-6e}
\prod_{i=0}^{k-1}(n+i)\;\Big|\;\prod_{i=0}^{k-1}(n+k+i)
\qquad\text{in }\mathbb Z?
\end{equation} Equivalently, \[
n(n+1)\cdots(n+k-1) \mid (n+k)(n+k+1)\cdots(n+2k-1).
\] Examples given: for $n=2$ one can take $k=5$, and for $n=3$ one can take $k=4$.
Quick literature/context check (browsing available)
The Erdős Problems site (Problem #389) records the question and notes that the smallest such $k$ (if it exists) grows quickly; computed values for $n$ up to $18$ are tabulated in OEIS A375071 (with an index shift). No general proof (or counterexample) is indicated there.
Attack plan
- Rewrite (eq:P389-main) into equivalent forms (factorials / binomial coefficients) to expose structure.
- Use $p$-adic valuations (Legendre/Kummer) to express the divisibility condition prime-by-prime.
- Check whether a simple constructive choice of $k$ (e.g. depending on $n$ via lcm/factorials/primorials) forces the valuation inequalities.
Work
Rewriting via factorials.
Let \[
L(n,k):=\prod_{i=0}^{k-1}(n+i)=\frac{(n+k-1)!}{(n-1)!},
\qquad
R(n,k):=\prod_{i=0}^{k-1}(n+k+i)=\frac{(n+2k-1)!}{(n+k-1)!}.
\] Then
(eq:P389-main) is the condition $L(n,k)\mid R(n,k)$, i.e.
\begin{equation}
\label{wsref-0-65-71-3a-50-33-38-39-2d-72-61-74-69-6f}
\frac{R(n,k)}{L(n,k)}
=\frac{(n-1)!(n+2k-1)!}{\left((n+k-1)!\right)^2}\in\mathbb Z.
\end{equation}
Binomial-coefficient form.
Using \[
\binom{n+k-1}{k}=\frac{(n+k-1)!}{(n-1)!\,k!}
\quad\text{and}\quad
\binom{n+2k-1}{k}=\frac{(n+2k-1)!}{(n+k-1)!\,k!},
\] we have \[
L(n,k)=k!\binom{n+k-1}{k},\qquad R(n,k)=k!\binom{n+2k-1}{k}.
\] Therefore
\begin{equation}
\label{wsref-0-65-71-3a-50-33-38-39-2d-62-69-6e-6f-6d-69-61-6c}
L(n,k)\mid R(n,k)
\iff
\binom{n+k-1}{k}\;\Big|\;\binom{n+2k-1}{k}.
\end{equation} This binomial formulation is often more convenient for $p$-adic valuation work.
Prime-by-prime formulation.
Let $v_p(\cdot)$ be the $p$-adic valuation. Then
(eq:P389-main) is equivalent to
\begin{equation}
\label{wsref-0-65-71-3a-50-33-38-39-2d-76-61-6c-75-61-74-69-6f-6e}
\forall p\ \text{prime}:\quad
v_p\left(R(n,k)\right)\ge v_p\left(L(n,k)\right).
\end{equation} Equivalently, using
(eq:P389-ratio), \[
\forall p:\quad
v_p((n+2k-1)!)+v_p((n-1)!)\ge 2v_p((n+k-1)!).
\] By Legendre's formula $v_p(N!)=\sum_{j\ge 1}\lfloor N/p^j\rfloor$, this becomes an explicit (but complicated) family of inequalities in $k$.
What I can verify unconditionally.
- The examples: $2\cdot 3\cdot 4\cdot 5\cdot 6=720$ divides $7\cdot 8\cdot 9\cdot 10\cdot 11=55440$ (quotient $77$), and $3\cdot 4\cdot 5\cdot 6=360$ divides $7\cdot 8\cdot 9\cdot 10=5040$ (quotient $14$).
- Computation (separate) shows the smallest $k$ for $n=4$ is already large ($k=207$), consistent with OEIS A375071 (after the index shift).
Why the natural "one-line" constructions fail.
A tempting sufficient condition for
(eq:P389-main) would be a bijection between the left block and right block such that each left term divides its matched right term. However, because the right block is only a shift by $k$, divisibility of the form $(n+i)\mid(n+k+j)$ forces rigid congruences and fails for most terms. Also, choices like $k=\mathrm{lcm}(1,\dots,n)$ or $k=n!$ do not empirically satisfy
(eq:P389-main) even for small $n$.
Verification
- (eq:P389-ratio) follows by substituting the factorial expressions for $L(n,k)$ and $R(n,k)$.
- (eq:P389-binomial) follows from $L=k!\binom{n+k-1}{k}$ and $R=k!\binom{n+2k-1}{k}$.
- (eq:P389-valuation) is the standard characterization of divisibility via $p$-adic valuations.
Final
UNRESOLVED. - (i) Strongest proved partial result: The divisibility condition is exactly the binomial divisibility $\binom{n+k-1}{k}\mid\binom{n+2k-1}{k}$, equivalently the integrality of the ratio in (eq:P389-ratio), and it reduces to the family of $p$-adic inequalities (eq:P389-valuation).
- (ii) First gap / obstruction: I did not find a construction of $k$ (as a function of $n$) that forces (eq:P389-valuation) simultaneously for all primes, nor a monotonicity argument that guarantees existence for sufficiently large $k$.
- (iii) Top 3 next moves: $1$ Use Kummer's theorem (carries in base $p$) to reinterpret $v_p\left(\binom{n+k-1}{k}\right)$ and $v_p\left(\binom{n+2k-1}{k}\right)$ and attempt to engineer $k$ so that carries only increase. $2$ Search for a group action / combinatorial partition that would make (eq:P389-binomial) obvious for a suitable $k$. $3$ Try to build $k$ inductively by forcing the valuation inequalities for primes up to a growing bound, using Chinese-remainder-type constraints.
- (iv) What a minimal counterexample would look like: An $n$ such that for every $k\ge 1$ there is some prime $p$ with $v_p\left(\binom{n+2k-1}{k}\right)<v_p\left(\binom{n+k-1}{k}\right)$. Empirically, if counterexamples exist they likely occur at modest $n$ but require very large search ranges in $k$.
Completion estimate
A full solution would be either an explicit constructive $k(n)$ with a proof of
(eq:P389-valuation) for all primes $p$, or a proof that some $n$ admits no such $k$. Both directions appear to require new structural insight into the ratio of the two binomial coefficients in
(eq:P389-binomial).