<s>[INST] Find the $k$ such that $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$. Find all positive integers $k$ such that for any positive integer $n$, $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$.
From olympiad problem
I'm curious So far no one to solve this problem,Maybe it is very difficult May be other reasons? But I really want to know how to solve this problem more easy?
 [/INST] The number of factors $2$ in a number $a!$ is:
$$
\left\lfloor \frac a 2 \right\rfloor
+
\left\lfloor \frac a 4 \right\rfloor
+
\left\lfloor \frac a 8 \right\rfloor
+ \cdots
$$
So we have to find all $k$ such that for every $n$, we have
$$
kn - n + 1 > 
\sum_{x=1} \left\lfloor \frac{kn}{2^x} \right\rfloor
-
\sum_{x=1} \left\lfloor \frac{n}{2^x} \right\rfloor
$$
Now, to save typing, I define $F(a) = \sum_{x=1} \left\lfloor \frac{a}{2^x} \right\rfloor$. So how much is $F(a)$ compared to $a$?
Lemma: $F(2^a) = 2^a-1$
Proof: We have $F(2^a) = 2^{a-1} + 2^{a-2} + \cdots + 1 = 2^a-1$.
$\blacksquare$
Lemma: If $b < 2^a$, then $F(2^a + b) = F(2^a) + F(b)$.
Proof: For every $x < a$, $\frac{2^a}{2^x}$ is an integer and thus
$$
\left\lfloor \frac{2^a + b}{2^x} \right\rfloor
=
\left\lfloor \frac{2^a}{2^x} \right\rfloor
+
\left\lfloor \frac{b}{2^x} \right\rfloor
$$
For every $x \geq a$, we have $\left\lfloor \frac{b}{2^x} \right\rfloor = 0$, so the equation holds as well.
$\blacksquare$
A consequence of this is that $a - F(a)$ is the number of ones in the binary representation of $a$.
So $kn - n + 1 > F(kn) - F(n)$ means that $kn - F(kn) \geq n - F(n)$, which means that the binary representation of $kn$ has at least as many ones as the one of $n$.
So it's obvious that $k = 2^a$ always works. I'll think of some reasons why other $k$s don't work shortly. 
</s>