# Let $n$ such that $\displaystyle{2^{n-2005}} | n!$

Let $n$ such that $\displaystyle{2^{n-2005}} | n!$

Prove that this number has at most $2005$ non-zero digits when written in base $2$.

-

## 1 Answer

there are $\sum_{k\ge 1} \lfloor \frac{n}{2^k}\rfloor$ 2s in $n!$. So we must have $n - 2005 \le \sum_{k\ge 1} \lfloor \frac{n}{2^k}\rfloor$. Now write $n = \sum_{i} 2^{\ell_i}$ in base $2$ with $\ell_1 < \ldots < \ell_m$. We have \begin{align*} \left \lfloor \frac{n}{2^k}\right\rfloor &= \sum_{i:\ell_i \ge k} 2^{\ell_i - k}\\ \sum_{k\ge 1} \left \lfloor \frac{n}{2^k}\right\rfloor &= \sum_{k\ge 1} \sum_{i:\ell_i \ge k} 2^{\ell_i - k}\\ &= \sum_{i=1}^m \sum_{k = 1}^{\ell_i} 2^{\ell_i - k}\\ &= \sum_{i=1}^m 2^{\ell_i} \sum_{k=1}^{\ell_i}2^{-k}\\ &= \sum_{i=1}^m 2^{\ell_i} \left(\frac{1 - 2^{-1-\ell_i}}{1-2^{-1}} - 1\right)\\ &= \sum_{i=1}^m 2^{\ell_i} \left(1 - 2^{-\ell_i}\right)\\ &= \sum_{i=1}^m 2^{\ell_i} - m\\ &= n - m \end{align*} So $n - 2005 \le n - m$, i. e. $m \le 2005$ as to be proved.

AB,

-
Wow!, that was quick. Is AB, similar to Q.E.D.? –  Kirthi Raman Mar 23 '12 at 13:21
No, "AB" means "allzeit bereit", it's the german Scout motto. –  martini Mar 23 '12 at 13:22
I thought of asking (it is something in german). Thanks much martini. –  Kirthi Raman Mar 23 '12 at 13:23