puzzler: binomial coefficients
Author Message
puzzler: binomial coefficients

In this thread on computing binomial coefficients, it was suggested to obtain
them by means of the exponent E(N,K,P) of each prime P in the prime
factorization of K!N.    A formula for this exponent is given in
Goetgheluck, P.  Computing binomial coefficients,
The Amer. Mathematical Monthly, April 1987, p. 360-365.
This formula is embodied in the following APL function BINEXP, where the
exponent is given by Z and NKK is the triple N,K,N-K.

{del}Z{<-}P BINEXP NNK
Z{<-}+/1{neg}1{neg}1+.{times}{floor}NNK{jot}.{divide}P*{iota}{floor}P{log}N
{del}
Note in particular that E(N,K,P)=1 if N-K <P <= N
and         =0 if N/2 <P <= N-K

The function BINOME will produce all the exponents in the factorization of N!K.

{del}Z{<-}K BINOME N;T;PRE
PRE{<-}PRIMESTO N        {lamp} any function giving all the primes to N
T{<-}{neg}1+(PRE>N{divide}2){iota}1
Z{<-}PRE>N-K{<-}K{min}N-K
Z[{iota}T]{<-}(PRE[{iota}T]) BINEXP {each}{enclose}N,K,N-K
{del}

For example, the exponents of the primes in 1000!6000 are obtained in about 0.4
sec. with APL68000 on a PowerMac or with APL2 under OS/2 on a Pentium 100.

Challenge: Goetgheluck notes that the exponent of the prime P in K!N is the
number of carries when summing N-K and K, both written in base P. It is
equivalently the number of borrows in the subtraction N-K  in base P.
Write a preferably non-looping function giving this number of borrows or of
carries.
--
Julien Constantin  Departement de Mathematiques et Informatique

Sat, 19 Sep 1998 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages