For all natural numbers $k$ the ratio $$ \frac{(2k)!}{(k!)^2}=\binom{2k}k $$ is an integer. From staring at the Pascal triangle long and hard, we know that these ratios grow rather quickly as $k$ increases. It is therefore natural to think that may be some factors from the numerator can be dropped in such a way that the ratio would still be an integer. More specifically, can we, for some carefully chosen $k$, leave out a chosen number of largest factors. In other words, given an integer $t>0$ does there exist a natural number $k$ such that $$\frac{(2k-t)!}{(k!)^2}\in\Bbb{Z}?$$

My curiosity about this comes from a question we had in May. The asker there had found the smallest $k$ that works for each of $t=1,2,\ldots,8$. In that question it was settled that with $t=9$ the smallest $k$ that works is $k=252970$.

It is natural to think about such divisibility questions one prime factor $p$ at a time. It is well known that if we write a natural number $m$ in base $p$, $$m=\sum_{i=0}^\ell m_ip^i$$ with the digits $m_i\in\{0,1,\ldots,p-1\}$, then the highest power of $p$ that divides $m!$ is equal to $$ \nu_p(m!)=\frac1{p-1}\left(m-\sigma_p(m)\right), $$ where $$\sigma_p(m)=\sum_{i=0}^\ell m_i$$ is the sum of "digits" of $m$ in base $p$. Written in this way, my question asks for a given $t$, whether there exists a $k$ such that the inequality $$ (2k-t)-\sigma_p(2k-t)\ge 2k-2\sigma_p(k) $$ holds for all primes $p\le k$.

As we have that slack one might expect this to be possible. But I'm not sure. One obstruction comes from primes just below $k$. If $k-(t/2)<p<k$, then $p^2$ is a factor in the denominator, but $2p$ is too large to appear as factor in the numerator, so $p^2\nmid (2k-t)!$. Occasionally a small prime is also problematic. It is not clear to me how to approach this. A construction may exist. The only thing this reminds me of is the elementary exercise $(k!)^{k+1}\mid (k^2)!$, but that doesn't seem to apply here.

In a comment under the answer to the linked question user metamorphy reports having confirmed this up to $t\le14$.

Edit/Note: The available evidence (see also Sil's comment under this question) suggests that, at least when looking for the smallest $k$ that works for a given $t$, whenever a chosen $k$ works for an odd number $t$, that same $k$ also works for $t+1$. If the main question proves to be too difficult to crack, steps towards explaining this phenomenon are also interesting.

  • 3
    $\begingroup$ In your second to last paragraph, "primes just below $k$" can be accounted for by simply choosing a large prime gap and setting $k$ at the end of it... $\endgroup$
    – abiessu
    Jul 9, 2020 at 13:02
  • 3
    $\begingroup$ @RossMillikan The other question doesn't show the existence of a valid $k$ for all $t$, only a faster way of computing the minimal valid $k$. $\endgroup$ Jul 10, 2020 at 14:10
  • 2
    $\begingroup$ This question was created to get more material for the Pearl Dive. $\endgroup$ Jul 11, 2020 at 12:56
  • 3
    $\begingroup$ @JoshuaP.Swanson I also had association with Catalan numbers. However the main difference is that each Catalan number is integer, but here we need to show that there exists $k$ such that $\binom{2k}{k}$ is divisible by $(2k)\cdot(2k - 1)\cdots(2k - t + 1)$ $\endgroup$
    – Smylic
    Jul 14, 2020 at 11:17
  • 3
    $\begingroup$ As for the further verification, $k=159329615$ works for $t \leq 16$ and $k=2935782898$ works for $t \leq 18$. Next $k$ must be greater than $15980000001$ per my calculations. Though this does not help much in revealing generic pattern, except that all these $k$ have very few and distinct prime divisors (i guess there is some probabilistic reason for that). $\endgroup$
    – Sil
    Jul 16, 2020 at 11:32

1 Answer 1


Note: this is not a complete solution, rather it is an approach that may provide insight or be workable into a solution.

Using the terms in the question, let $t\ge 1$ be given and consider $\frac{(2k-t)!}{(k!)^2}$. If we take $q=(t+1)\#+1+t$ then each of the numbers $q-t+1,q-t+2,\dots, q$ has a factor in common with $q-t-1$. If $2k\equiv q+\{0,1\}\mod (t+1)\#$ and $2k\ge q$ then there will be no primes $p\in [2k-t+1, 2k]$ and therefore if $p\mid k!$ then $p^2\mid (2k-t)!$. (Note that odd $q$ means $2k\equiv q+1\mod (t+1)\#$ and $(q+1, (t+1)\#)\gt 2$.) Moving forward, assume that $2k\equiv_{(t+1)\#}t+1+(t\mod 2)$.

Next consider a factor $p^r\mid k!$ such that $p^{2r}\nmid (2k-t)!$, which means that $p^u\mid x,x\in[2k-t+1,2k]$. Begin with $u=2$. If $p^2\ge t$ then we must move $p^2$ into the given arrangement also, which can be accomplished by $p^2\equiv 2k-q-[1,t]\mod (t+1)\#$. This same process can be applied for each $p^u > t$. More specifically, let $u_p=\lfloor\log_p t\rfloor +1$, then $p^{u_p} > t$ for each given $p$ and the specified modulus would be along the lines $$q=t+1+\prod_{p\le t}p^{\lfloor\log_p t\rfloor+1}$$ with $2k\ge q+\{0,1\}$. This value can probably be simplified as $2k\ge t!+t+\{1,2\}$.

In order to use this further it might be provable that each prime increases its total factor count of $\binom{2n}n$ as $n$ increases, or as $n$ increases in some patterned manner, so that a bound can be determined. Specifically, it is clear in the patterns that for $p=2$ the quantity $\binom{2^n-2}{2^{n-1}-1}$ has $n-1$ factors of $2$, while for $p>2$ the quantity $\binom{p^n+1}{\frac{p^n+1}2}$ has $n-1$ factors of $p$. There are specific repeating patterns of each prime up to each of these particular boundaries, but I have not been able to tame them as yet. However, the patterns appear to present a form of "modular arithmetic" which seems to have potential for leveraging into a value for $2k$ for a given value of $t$, e.g., every $3$rd $n$ in $\binom{2n}n$ or every $5$th, etc.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .