Find the highest power of 2 dividing n

[whodsow]

Hi.
I have a question.
I know the rule of the hightest power of 2 dividing n!, the highest power means if $$2^{k}|n!$$, k is the greatest value. For example,
n the hightest power of 2 dividing n!
--------------------------------------
1 0
2 1
3 1
4 3
5 3
6 4
7 4
8 7
9 7
10 8
11 8
12 10
13 10
14 11
15 11
16 15
17 15
18 16
19 16
20 18
21 18
22 19
23 19
24 22
25 22
26 23
27 23
28 25
29 25
30 26
31 26
32 31
33 31

Let f(n) is the highest power of 2 dividing n!, I think if $$2^{k}=n$$, then $$f(n) = 2^{k}-1$$, else let $$n=2^{k_{1}}+2^{k_{2}}+...++2^{k_{r}}$$, then $$f(n)=f(2^{k_{1}})+f(2^{k_{2}})+...+f(2^{k_{r}})=2^{k_{1}}-1+2^{k_{2}}-1+...+2^{k_{r}}-1$$, more verification of n shows my rule is correct, but I can't prove that.
Help me to prove my rule. thanks.

 

[CRGreathouse]

Split it into subproblems. Showing that (2^k)! is divisible by 2^(2^k - 1) but not by 2^(2^k) can be done by induction, starting with a base case of 1! being divisible by 1 but not by 2. For the inductive step, use that n! has a factor of 2 every 2, a factor of 4 every four, and so on, up to a factor of 2^k every 2^k (i.e. exactly once). This is a geometric series.

 

[whodsow]

thank your hint, CRGreathouse.
I will try to prove it.

 

[ramsey2879]

Hi.
I have a question.

Let f(n) is the highest power of 2 dividing n!, I think if $$2^{k}=n$$, then $$f(n) = 2^{k}-1$$, else let $$n=2^{k_{1}}+2^{k_{2}}+...++2^{k_{r}}$$, then $$f(n)=f(2^{k_{1}})+f(2^{k_{2}})+...+f(2^{k_{r}})=2^{k_{1}}-1+2^{k_{2}}-1+...+2^{k_{r}}-1$$, more verification of n shows my rule is correct, but I can't prove that.
Help me to prove my rule. thanks.

Did you try to corrolate your rule with the following
$$f(n) = \sum_{i = 1}^{b} \Left[ \frac{n}{2^i}\Right]$$
where the brackets stand for the foor function, and b is the highest power of 2 less than or equal to n

 

[whodsow]

Did you try to corrolate your rule with the following
$$f(n) = \sum_{i = 1}^{b} \Left[ \frac{n}{2^i}\Right]$$
where the brackets stand for the foor function, and b is the highest power of 2 less than or equal to n

oh, thank you.
I am a beginner, just starting to learn number theorem, I did not know this formulation until you told me.