- #1
whodsow
- 12
- 0
Hi.
I have a question.
I know the rule of the hightest power of 2 dividing n!, the highest power means if [tex]2^{k}|n![/tex], 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 [tex]2^{k}=n[/tex], then [tex]f(n) = 2^{k}-1[/tex], else let [tex]n=2^{k_{1}}+2^{k_{2}}+...++2^{k_{r}}[/tex], then [tex]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[/tex], more verification of n shows my rule is correct, but I can't prove that.
Help me to prove my rule. thanks.
I have a question.
I know the rule of the hightest power of 2 dividing n!, the highest power means if [tex]2^{k}|n![/tex], 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 [tex]2^{k}=n[/tex], then [tex]f(n) = 2^{k}-1[/tex], else let [tex]n=2^{k_{1}}+2^{k_{2}}+...++2^{k_{r}}[/tex], then [tex]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[/tex], more verification of n shows my rule is correct, but I can't prove that.
Help me to prove my rule. thanks.