/* bc program binomial. See P. Goetgheluck, Computing Binomial Coefficients, American Math. Monthly 1987, 360-365. * binomial_p(n,k,p) computes the power e of a prime p dividing n choose k. * e is the number of borrows in the subtraction n-k in base p. * Here n>k>0. */ define binomial_p(n,k,p){ auto e,r,a,b,f e=0;r=0 if(k>n/2){ k=n-k } if(p>n-k){ return (1) } if(p>n/2){ return (0) } f=sqrt(n) if(p>f){ if(n%p < k%p){ return(1) }else{ return(0) } } while(n){ a=n%p; n=n/p b=k%p+r; k=k/p if(ap[2047]){ print "n > 17863\n" return } if(k<=0){ print "k <= 0\n" return } if(n<=k){ print "n <= k\n" return } i=0 s=0 while(p[i]<=n){ /* there exists an i, 0<=i<=2047, satisfying p[i]>n */ p=p[i] e=binomial_p(n,k,p) if(e){ if(s){ if(e>1){ print " x ",p,"^",e }else{ print " x ",p } }else{ if(e>1){ print p,"^",e }else{ print p } } if(s%10==0 && s){ print "\n" } s=s+1 } if(i==2047){ break }else{ i=i+1 } } print "\n" print "the number of prime factors of ", n, " choose ", k, " is " return(s) }