Find the greatest powers of $2$ dividing $10!$, $20!$, $30!$, $40!$

Question

I'm trying to find the greatest powers of $2$ dividing $10!$, $20!$, $30!$, $40!$, as part of a basic number systems course.

I'm rather lost with this question. For $10!$ I tried writing the terms out and just extracting powers of $2$ manually, getting $2^8$ as the highest powers of $2$, with $10! = (2^8)(14175)$ as the result.

I'm fairly confident that the answer is correct (although I'm not sure, so confirmation of that would be great!), but this method is rather crude for larger numbers, so I suspect that it isn't the right way to do it.

If anyone can point me in the right direction I would be very grateful.

Answer 1

One way to do it is to count the ammount of numbers divisible by $2,4,8,...$ between $1$ and $n$. For example, look at $40!$:
There are $\left\lfloor\frac{40}{32}\right\rfloor=1$ numbers divisible by $32$ (between $1$ and $40$) and each contributes $2^5$.
There are $\left\lfloor\frac{40}{16}\right\rfloor=2$ numbers divisible by $16$ and each contributes $2^4$.
There are $\left\lfloor\frac{40}{8}\right\rfloor=5$ numbers divisible by $8$ and each contributes $2^3$.
There are $\left\lfloor\frac{40}{4}\right\rfloor=10$ numbers divisible by $4$ and each contributes $2^2$.
There are $\left\lfloor\frac{40}{2}\right\rfloor=20$ numbers divisible by $2$ and each contributes $2^1$.
Hence the biggest power that will divide $40!$ is $1+2+5+10+20=38$ (i.e. $(2^5)^1(2^4)^2(2^3)^5(2^2)^{10}(2^1)^{20}=2^{38}$), since that way a number divisible by $32$ is counted $5$ times, a number divisible by $16$ is counted $4$ times and so on.
Applying the same method to $10!$ you get: $1$ number divisible by $8$, $2$ numbers divisible by $4$, $5$ numbers divisible by $2$. So total of $1+2+5=8$. Hence $2^8$ is the highest power.

Answer 2

For any prime $p$ and integer $n$, let $$ n=d_0+d_1p+d_2p^2+d_3p^3+\dots+d_kp^k\tag{1} $$ where $0\le d_j\lt p$. $(1)$ is the base-$p$ representation of $n$.

The number of multiples of $p$ not greater than $n$ would be $$ \left\lfloor\frac np\right\rfloor=d_1p^0+d_2p^1+d_3p^2+d_4p^3+\dots+d_kp^{k-1}\tag{2} $$ The number of multiples of $p^2$ not greater than $n$ would be $$ \left\lfloor\frac n{p^2}\right\rfloor=\hphantom{d_1p^0+}d_2p^0+d_3p^1+d_4p^2+\dots+d_kp^{k-2}\tag{3} $$ The number of multiples of $p^3$ not greater than $n$ would be $$ \left\lfloor\frac n{p^3}\right\rfloor=\hphantom{d_1p^0+d_2p^1+}d_3p^0+d_4p^1+\dots+d_kp^{k-3}\tag{4} $$ and so forth.

$(2)$ only counts each multiple of $p^2$ once. To count each multiple of $p^2$ twice, we need to add $(3)$. This only counts each multiple of $p^3$ twice. To count each multiple of $p^3$ three times, we need to add $(4)$, and so on.

After adding up $(2)$, $(3)$, $(4)$, and so on, the coefficient of $d_j$ is $$ p^{j-1}+p^{j-2}+p^{j-2}+\dots+p^0=\frac{p^j-1}{p-1}\tag{5} $$ Thus, the sum of $(2)$, $(3)$, $(4)$, and so on is $$ d_0\frac{p^0-1}{p-1}+d_1\frac{p^1-1}{p-1}+d_2\frac{p^2-1}{p-1}+\dots+d_k\frac{p^k-1}{p-1}=\frac{n-\sum d_j}{p-1}\tag{6} $$ Therefore, the number of factors of $p$ in $n!$ is $$ \frac{n-\sum d_j}{p-1}\tag{7} $$ where $\sum d_j$ is the sum of the base-$p$ digits of $n$.

Examples

For $p=2$, $10=1010_{\text{two}}$, so $\sum d_j=2$. There are $\frac{10-2}{2-1}=8$ factors of $2$ in $10!$

For $p=2$, $20=10100_{\text{two}}$, so $\sum d_j=2$. There are $\frac{20-2}{2-1}=18$ factors of $2$ in $20!$

For $p=2$, $30=11110_{\text{two}}$, so $\sum d_j=4$. There are $\frac{30-4}{2-1}=26$ factors of $2$ in $30!$

For $p=2$, $100=1100100_{\text{two}}$, so $\sum d_j=3$. There are $\frac{100-3}{2-1}=97$ factors of $2$ in $100!$