World!Of
Numbers

WON plate
89 |

[ 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 = 27 x 34 x 5 x 7

Take N = 79
79{10} = 1001111{2}
79! = 274 x 336 x 518 x 712 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))/(q-1) = number of prime factors q in N!

N - S_q(N) = (q-1) (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 ?



A000089 Prime Curios! Prime Puzzle
Wikipedia 89 Le Nombre 89 Numberland 89














[ TOP OF PAGE]


( © All rights reserved )
Patrick De Geest - Belgium - Short Bio - Some Pictures
E-mail address : pdg@worldofnumbers.com