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  
 
 [ 1 post ] 

 Relevant Pages 

1. Puzzler: Binomial Coefficients

2. Puzzler: Binomial Coefficients

3. Puzzler: Binomial Coefficients

4. Puzzler : Binomial Coefficients

5. Binomial Coefficients

6. Binomial coefficients

7. binomial coefficient (by hand)

8. binomial tree

9. LogoFE and binomial distribution

10. ? generating random uniform and binomial random deviates for BIG integers

11. Help to create a binomial distribution

12. Negative Binomial Approximations

 

 
Powered by phpBB® Forum Software