Log In

Largest power of 2

Posted on: September 30th, 2013 by
4

What is the greatest power of two that is a factor of:
19!
130!
Can you do both of the above mentally i.e w/o pencil/paper, computer etc?

- via Sid Hollander


4 Responses to Largest power of 2

  1. Lizard had this to say about that:

    Repeatedly divide the given number by two, rounding down, and add up the results. The reasoning is as follows:
    Of the numbers {1,...,19}, [19/2] = 9 are even and therefore contribute a 2 to the factorization of 19!.
    Of those, [9/2] = 4 are multiples of 4 and therefore contribute another factor of 2.
    Of those, [4/2] = 2 are multiples of 8 and contribute another factor of 2.
    Of those, [2/2] = 1 is a multiple of 16 and contributes another factor of 2.
    So 2^(9+4+2+1) = 2^16 is the largest power of 2 that divides 19!.

    A related puzzle: Show that for all natural numbers N,
    N = (the largest k for which 2^k divides N!) + (the number of ones in the binary representation of N). E.g. 19 = 16 + 3.

    • Lizard had this to say about that:

      Or more generally:
      N = (b - 1) * (the largest k for which b^k divides N!) + (the sum of the digits in the base b representation of N)

      • Sid Hollander had this to say about that:

        And still another related problem,
        Consider the generation of n rows of Pascals triangle and the coefficients of (a+b)^n as n goes from 0 to ...

        i.e rows
        1 0
        1 1 1
        1 2 1 2
        1 3 3 1 3

        the number of odd coefficients is equal to

        2^(sum of 1's in binary representation of n)

        Example. n=3 = 11 base 2. sum of 1's =2
        2 squared =4 odd coefficients in row 3.
        row 128 has 2 odd numbers (the 1's).

        These last items thanks to French Mathematician Adrien Legendre (1752-1833)

        Anyone for proofs of same?

        • Sid Hollander had this to say about that:

          Sorry for the messed up triangle. The right most terms were in a column labeled Rows.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}