Re: n! = a! b!

From: KRamsay (kramsay_at_aol.com)
Date: 09/10/04 

Date: 10 Sep 2004 22:36:11 GMT

In article <cht42f$icv$1@newslocal.mitre.org>, lewis@PROBE.MITRE.ORG (Keith A.
Lewis) writes:
|"The Last Danish Pastry" <clivet@gmail.com> writes in article
|<2qb108Ftp23lU1@uni-berlin.de> dated Thu, 9 Sep 2004 13:35:19 +0100:
|>Let c(x) be the number of ones in the binary represenation of x.
|>If n!=a!b! then a+b-n = c(a)+c(b)-c(n).
|
|Apparantly true, but why?

Because the number of times 2 divides a! (i.e., the largest k such
that 2^k divides a!) is a-c(a). This can be shown by induction on
a. If a is even, 2 divides a! and (a+1)! equally many times, and
c(a+1)=c(a)+1. If a is odd and 2 divides a+1 k times, then there
are k carries when we add 1 to a in binary, so c(a+1)=c(a)-k+1,
while 2 divides (a+1)! k more times than it divides a!.

So the number of times 2 divides n! is n-c(n) = (a-c(a))+(b-c(b)).

Keith Ramsay

Quantcast