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

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.

-

marked as duplicate by Did, TMM, J. M., vonbrand, MicahMar 27 '13 at 4:14

Use de Polignac's formula. For example, for $40!$ it produces $20+10+5+2+1=38$ and for $10!$ it produces $5+2+1=8$ as answer. – Hagen von Eitzen Oct 21 '12 at 12:47
There is a recent similar problem in hich I tried to give the intuition behind the "shortcut" way of computing the highest power of a prime $p$ (in that case $5$) that divides $n!$. – André Nicolas Oct 21 '12 at 17:54

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!$

-
Thank you for this explanation, it helped me see where I was going wrong! Unfortunately I don't really understand it. I think I can follow the derivation, but I don't understand the examples - what does 10 = 1010two mean? And how can the sum of dj, when each term has been defined as between 0 and p-1, be 2? – Richard Oct 21 '12 at 14:17
@Richard: $10=1010_{\text{two}}$ means that $10$ (ten) is equal to $1010$ in base two. The sum of the base two digits is $1+0+1+0=2$. Does that help? – robjohn Oct 21 '12 at 14:25
Ohhhhhh! That makes perfect sense, thank you! I'm just not used to working in other bases! – Richard Oct 21 '12 at 14:28

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.

-
Thank you for your help, I've tried both this method and the Polignac formula, but for 20! I get different answers from each! For 10! and 40! they agree, but for 20! this method gives me 2^30, while Polignac gives me 2^18, which is also what I get if I try my original method of manually going through and extracting factors of 2. And yet 20!/2^30 is an integer! I'm very confused by this, could you (or anyone) explain what's going on here? – Richard Oct 21 '12 at 13:50
Actually, I now see that the two methods are the same, and I was in fact misunderstanding this method - they both now give me 2^18. So now all that troubles me is that 20! is still divisible by 2^30, which doesn't make sense! – Richard Oct 21 '12 at 13:59
@Richard: What do you get for $20!/2^{30}$? I get $2265816562.04224$ Notice that $20!/2^{18}=9280784638125$, which is odd, so $20!$ cannot be divisible by $2^{30}$. – robjohn Oct 21 '12 at 15:31