Find all $k \in \mathbb{Z}^+$ that satisfy every $n \in \mathbb{Z}^+$ s.t. $2^{(k-1)n+1} \nmid \frac{(kn)!}{n!}$ Problem : Find all positive integers k that satisfy every positive integer n that $ 2^{(k-1)n+1}$  is not a divisor of   $\frac{(kn)!}{n!}$
This is all i did :
Legendre's formula : $v_2$(n!) = n-$S_n$(2).(where $S_n$(2) is the sum of the digits of n in the 2 . factorization system )
What must prove is equivalent to :
$v_2$( $\frac{(kn)!}{n!}$) $\lt$ (k-1)n+1
kn-$S_{kn}$(2)  -n+$S_n$(2) < (k-1)n+1
$S_n$(2)-$S_{kn}$(2)<1;
So , we need to find a positive integer k such that for every positive integer n :  $S_n$(2)-$S_{kn}$(2)<1;
It is easy to see that for k = $2^z$  then $S_n$(2)-$S_{kn}$(2)=0  (satisfied with z being an integer)
At this point I am completely out of ideas, maybe k is just like that, but I still can't prove that hypothesis. This is a really interesting and fascinating issue for me . Can you give me some ideas or suggestions?
 A: There is a theorem that says that $v_p(n!)=\frac{n-S_p(n)}{p-1}$, where $S_p(n)$ is the sum of the digits in the base $p$ representation of $n$. Using this we get $v_2\frac{(kn)!}{n!}=(k-1)n+(S_p(n)-S_p(kn) )$.
So the number $k$ must satisfy that $kn$ has sum of digits greater than or equal to $n$ for any $n$ (in binary).
Notice that $k$ satisfies this if and only if $2k$ satisfies this, so we must only prove that the only odd integer that works is $k=1$.
Suppose an odd $k>1$ works. Let $m$ be a multiple of $k$ with the least possible number of "one" bits (suppose it has $v$ bits). Write $m=2^a+b$ with $2^a>b$. Notice that the number $w=2^{a+s\varphi(k)}+b$ is also a multiple of $k$ with $v$ bits for every $s\in \mathbb Z^+$.
We now prove that $w/k$ must have more than $v$ bits for sufficiently large $s$.We proceed by contradiction, pick $s$ so that $w/k$
must have at least $z$ consecutive zeros in its binary representation, where $z$ is equal to the length of the base $2$ representation of $k$. Then the number of bits in $w/k\times k$ is equal to the sum of the bits of $k$ multiplied by each of the two parts of $w/k$, and this is at least $2v$. This is a contradiction.
A: Well here is an attempt...
$\frac{(kn)!}{n!}$ means there are $kn-n = n(k-1)$ numbers left meaning $\frac{n(k-1)}{2}$ evens and  $\frac{n(k-1)}{2}$ number of 2's in the number and  $\frac{n(k-1)}{4}$ number of more 2's (from the numbers with 4 as a multiple) and  $\frac{n(k-1)}{8}$ number of more 2's (from the numbers with 8 as a multiple) and on and on......
Such that, $$n(k-1)\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+.....\right) = n(k-1)$$
which will still be not equal to the number of 2's in $2^{(k-1)n} \times 2 $
So all positive integers could be $k$ (Some logistics are off but you get the point.)
