Binomial coefficients modulo m

I have recently written a Python function to compute binomial coefficients modulo m where m is a positive integer. It uses Lucas' theorem, Kummer's theorem, a generalization of Lucas' theorem for prime powers due to Davis and Webb [1], and the Chinese Remainder Theorem. The code is available as part of the pypi OEISsequences module: oeissequences · PyPI

After installing this modulo, it can be used as follows:

from oeis_sequences.OEISsequences import binom_mod

print(binom_mod(27449,13722,38)) # computes binomial(27449,13722) modulo 38 = 34

print(binom_mod(179424671,89712333,1062882)) # computes binomial(179424671,89712333) modulo 1062882 = 734832

This function is more efficient than computing the binomial coefficient (n,k) (using e.g., the Python function comb) and then taking the remainder with respect to m, especially when n and k are much larger than m and binomial(n,k) is a prohibitively large number. 

[1] Kenneth S. Davis and William A. Webb, "Lucas' Theorem for Prime Powers", Europ. J. Combinatorics (1990) 11, 229-233. 

Sum of rows of Pascal's triangle modulo 8

 Pascal's triangle modulo $m$ can present interesting numerical structures. For instance, for $m=2$, the resulting triangle is the fractal Sierpinski's triangle. We consider the sum of the $n$-th row of Pascal's triangule mod 8. 

This sum (OEIS A385285) is defined as $a(n) = \sum_{k=0}^n \left[\left(\begin{array}{c}n\\k\end{array}\right) \mod 8\right]$

In particular, we construct a formula for this sum using the results in Ref. [1]. We follow the notation in Ref. [1]. Let $N_n(t,m)$ be defined as the numbers of integers in the $n$-th row of Pascal's triangle that is congruent to $t$ modulo $m$.

Then $a(n) = \sum_{k=1}^7 kN_n(k,8)$. We split this sum into three parts: $x_1 = 4N_n(4,8)$, 

$x_2 = 2N_n(2,8)+6N_n(6,8)$ and $x_3 =  N_n(1,8)+3N_n(3,8)+5N_n(5,8)+7N_n(7,8)$.

Defne $v_i$ and $s_i$ as the length of the $i$-th block of $0$'s (resp. $1$'s) in the binary representation of $n$. For a binary string $s$, let $n_s$ denote the number of occurrences of $s$ in the binary representation of $n$. In particular, $n_1$ is the Hamming weight of $n$ (OEIS A000120). Let $r=2^{n_1}$. This is also known as Gould's sequence or Dress's sequence (OEIS A001316). We will show that $a(n)$ is divisible by $r$.

The following results were shown in Ref. [1]:

$x_1 = 4N_n(4,8) = r(4n_{001}+n_{011}+n_{01}(n_{01}-1)/2)$.

$2N_n(2,8) = \left\{\begin{array}{ll}r(n_{01}-n_{001}) & \mbox{if } n_{11}=0\\r((n_{01}-n_{011})/2+n_{0011}) & \mbox{if } n_{11}=1\\r(n_{01}/2) & \mbox{if } n_{11}\geq 2\end{array}\right.$

$6N_n(6,8) = \left\{\begin{array}{ll}3r(n_{001}) & \mbox{if } n_{11}=0\\3r((n_{01}+n_{011})/2-n_{0011}) & \mbox{if } n_{11}=1\\3r(n_{01}/2) & \mbox{if } n_{11}\geq 2\end{array}\right.$

This implies that

$x_2 = \left\{\begin{array}{ll}r(n_{01}+2n_{001}) & \mbox{if } n_{11}=0\\r(2n_{01}+n_{011}-2n_{0011}) & \mbox{if } n_{11}=1\\r(2n_{01}) & \mbox{if } n_{11}\geq 2\end{array}\right.$

For the cases $N_n(i,8)$ where $i$ is odd, [1, Theorem C] splits them into 13 cases. Combining the results of these 13 cases to derive $x_3$, we get the following table:

Case No.    $x_3$