Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Find the highest power of 2 dividing n!

  1. Oct 20, 2007 #1
    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.
     
  2. jcsd
  3. Oct 20, 2007 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Oct 20, 2007 #3
    thank your hint, CRGreathouse.
    I will try to prove it.
     
  5. Oct 20, 2007 #4
    Did you try to corrolate your rule with the following
    [tex] f(n) = \sum_{i = 1}^{b} \Left[ \frac{n}{2^i}\Right] [/tex]
    where the brackets stand for the foor function, and b is the highest power of 2 less than or equal to n
     
  6. Oct 21, 2007 #5
    oh, thank you.
    I am a beginner, just starting to learn number theorem, I did not know this formulation until you told me.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Find the highest power of 2 dividing n!
  1. Find all n^3-n = d^2+d (Replies: 3)

Loading...