Factorials and Binary Numbers
[ January 13, 2001 ]
On June 20, 1999 I received a message from 11th grader Kiwoo Song
asking for extra material related to a particular theorem...
Honesty compells me to say I couldn't help him further with the project
but found the theorem nevertheless very intriguing as it relates two familar concepts
in a very interesting way namely factorials and binary numbers.
Any natural number N is equal to the sum of the numbers of 1's in its
binary representation and the number of 2's in the prime factorization of N!
A few worked out examples to illustrate the topic
Take N = 9
9_{{10}} = 1001_{{2}}
9! = 362880 = 2^{7} x 3^{4} x 5 x 7
Take N = 79
79_{{10}} = 1001111_{{2}}
79! = 2^{74} x 3^{36} x 5^{18} x 7^{12} x ... x 73 x 79
Just like Kiwoo Song then I am now trying to find information
(references, sources) that relates to the above theorem.
On [ February 19, 2001 ] none other than Ki Song himself emailed me that he
found back his notes (from 3 years ago).
It was Legendre that first found the results in 1808.
He said that the number of prime factors q in N! is equal to the expression:
Sum N/q^i from i=0 to inf = [N/q] + [N/q^2] + [N/q^3] + ... + [N/q^n] + 0 + 0 + ...
where [x] = greatest integer less than or equal to x.
He also said that the difference between the number N and the sum
of digits of N in base q divided by q  1 is equal to the expression above.
So, if S_q(N) = the sum of digits of N in base q, we can write:
(N  S_q(N))/(q1) = number of prime factors q in N!
N  S_q(N) = (q1) (number of prime factors q in N!)
N = S_q(N) + (q  1) (number of prime factors q in N!)
If q = 2, we have
N = S_2(N) + (2  1) (number of prime factors 2 in N!)
N = (the number of 1s in the binary expression of N) +
(number of factors 2 in N!)

The number of 1s in the binary expression of N is also known as
the Hamming Weight.
The proof is not too difficult to find. Can it be found on the web ?