## 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."}