[ January 13, 2001 ]
Factorials and Binary Numbers
Kiwoo Song

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⁷ x 3⁴ x 5 x 7

Take N = 79
79_{10} = 1001111_{2}
79! = 2⁷⁴ x 3³⁶ x 5¹⁸ x 7¹² 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:

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 ?