BinomialCoefficients 1.13

documentation notebook

Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

BinomialCoefficients is a package containing implementations of several theorems on the residues and divisibility properties of binomial coefficients.
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.
The last section lists the theorems used by each symbol.

To use BinomialCoefficients, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)

<<BinomialCoefficients`

Arithmetic properties of binomial coefficients

When every entry of Pascal's triangle is reduced modulo a prime or prime power, a nested structure is produced.  For example, reducing modulo 2 produces the familiar Sierpiński sieve:

Column[Timing[ArrayPlot[Table[Mod[Binomial[n,m],2],{n,0,255},{m,0,n}]]]]

The symbols in this package compute various properties of these structures.

BinomialMod reduces a binomial coefficient modulo k using an indirect method.

Mod[Binomial[10,5],20]

BinomialMod[10,5,20]

For small numbers this is generally slower than the direct method, but for numbers of a suitable size the indirect method is faster.

Column[Timing[ArrayPlot[Table[BinomialMod[n,m,2],{n,0,255},{m,0,n}]]]]

In some cases there are faster ways than using the direct method:

Column[Timing[ArrayPlot[Table[Boole[BitAnd[BitNot[n],m]==0],{n,0,255},{m,0,n}]]]]

The symbol BinomialExponent corresponds to computing IntegerExponent of a Binomial.

IntegerExponent[Binomial[10,5],2]

BinomialExponent[10,5,2]

BinomialResidueCount counts the binomial coefficients on the nth row of Pascal's triangle that have a certain remainder when divided by k.
For example, this is the number of binomial coefficients on row 20 that are of the form 3i+1:

BinomialResidueCount[20,3,1]

Here is the 20th row modulo 3:

Mod[Binomial[20,Range[0,20]],3]

BinomialResidueCount also counts binomial coefficients on the nth row that are not divisible by k:

BinomialResidueCount[20,3]

It can also give answers for symbolic n in terms of the number of occurrences of various subwords in the base-p representation of n:
(The symbol DigitsCount belongs to my IntegerSequences package.)

BinomialResidueCount[n,3]

Package symbols

BinomialComplementMod

?BinomialComplementMod

Mod[((Binomial[1000,373])/(7^(IntegerExponent[Binomial[1000,373],7]))),49]

BinomialComplementMod[1000,373,49]

BinomialExponent

?BinomialExponent

IntegerExponent[Binomial[1000,373],2]

BinomialExponent[1000,373,2]

Function[k,And@@Flatten[Table[BinomialExponent[n,m,k]==IntegerExponent[Binomial[n,m],k],{n,0,20},{m,0,20}]]]/@Range[2,5]

Kummer’s theorem says that the exponent of p dividing Binomial[n,m] is the number of carries involved in adding m and n-m in base p.

With[{p=3},And@@Flatten[Table[BinomialExponent[n,m,p]==Carries[m,n-m,p],{n,0,20},{m,0,n}]]]

However, for speed, BinomialExponent uses Legendre’s formula rather than explicitly counting carries:

AbsoluteTiming[Table[Carries[m,n-m,p],{p,Prime[Range[10]]},{n,0,100},{m,0,n}];]

AbsoluteTiming[Table[BinomialExponent[n,m,p],{p,Prime[Range[10]]},{n,0,100},{m,0,n}];]

BinomialMod

?BinomialMod

Mod[Binomial[1000,729],19]

BinomialMod[1000,729,19]

BinomialResidueCount

?BinomialResidueCount

Count the entries on the billionth row of Pascal's triangle in each nonzero residue class modulo 7:

BinomialResidueCount[(10^9),7,Range[6]]

Compute the number of entries on the billionth row of Pascal's triangle that are not divisible by 7:

BinomialResidueCount[(10^9),7]

Compute a formula for the number of nonzero entries on row n of Pascal's triangle modulo 8 for symbolic n:

BinomialResidueCount[n,8]

Carries

?Carries

Carries[999,1,10]

Carries[999,1,10,1]

CoprimeFactorial

?CoprimeFactorial

Times@@Range[1,32,2]

CoprimeFactorial[32,2]

CoprimeFactorial[Range[10],5]

Implementation details

BinomialComplementMod[n,m,p] uses Anton's theorem.
BinomialComplementMod[n,m,(p^α)] uses Granville's theorem.

BinomialExponent[n,m,p] uses Legendre’s formula.

BinomialMod[n,m,p] uses Lucas' theorem.
BinomialMod[n,m,(p^α)] uses Granville's generalization of Lucas' theorem.
When k is not a prime power, BinomialMod[n,m,k] uses Granville's theorem for each prime power factor of k and reconstructs the residue using the Chinese remainder theorem.

BinomialResidueCount[n,p,r] uses a theorem of Garfield and Wilf.
BinomialResidueCount[n,(p^α)] uses Rowland's generalization of Fine's theorem.
In other cases, BinomialResidueCount[n,k,r] and BinomialResidueCount[n,k] use BinomialMod to explicitly tally residues.