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$

Oblong pandigital numbers

In this blogpost, I wrote about pandigital numbers (numbers in base n>1 that uses the numbers 0 to n-1 exactly once) that are also squares and a nice result of Adam Partridge that showed such square pandigital numbers do not exist if n is odd and n-1 has an even 2-adic valuation. A different approach to prove this result can be found in this article. It turns out that a similar result exists for oblong (or pronic) pandigital numbers.

Theorem: There are no oblong pandigital numbers in base n if n ≡ 3 (mod 4). 

Proof: Since nᵃ ≡ 1 (mod n-1), k ≡ m (mod n-1), where m is the digit sum of k in base n. Thus for a number k with every digit exactly once, k ≡ n(n-1)/2 (mod n-1).

Suppose n ≡ 3 (mod 4), i.e. n=2q+1 for some odd q. Then n(n-1)/2 = 2q²+q. Since n-1 = 2q, this means that n(n-1)/2 ≡ q (mod n-1). As q is odd, m(m+1) is even and n-1 is even, this implies that m(m+1) ≠ q (mod n-1) and thus m(m+1) is not a number with every digit exactly once and the proof is complete.

Conjecture: There are oblong pandigital numbers in base n if n !≡ 3 (mod 4).

Nearest integer with the same Hamming weight

Theorem: For a positive integer n, the nearest integer not equal to n with the same Hamming weight as n is larger than n if and only if n is odd.

Proof: If n is of the form 2ᵏ-1, then n is odd and there are no smaller positive integers with the same Hamming weight as n and the nearest integer not equal to n with the the same Hamming as n is equal to (3n+1)/2 > n.

Let us denote a(n) as the smallest integer > n with the same Hamming weight as n. For n not of the form 2ᵏ-1, let us denote b(n) as the largest integer < n with the same Hamming weight as n. Let us denote c(n) as the nearest integer not equal to n with the same Hamming weight as n.

If n is of the form (2ᵏ-1)*2ᵐ for some k, m>0, then n is even and in binary is of the form 11..1100..00 and a(n) = 2ᵏ⁺ᵐ+2ᵏ⁻¹-1, i.e. 100..0011..11 in binary. On the other hand, b(n) = (2ᵏ⁻¹-1)*2ᵐ⁺¹+2ᵐ⁻¹, i.e. 11..110100..00 in binary. Thus a(n)-n = 2ᵏ⁻¹-1+2ᵐ ≥ 2ᵐ and n-b(n) = 2ᵐ⁻¹ < 2ᵐ. Therefore c(n) = b(n).

If n is not of the form (2ᵏ-1)*2ᵐ, then n in binary is of the form xxx...xxx0yyy...yyy, where xxxxxx and yyyyy are both not all zeros. If yyy...yyy is of the form 2ʳ-1, then b(n) must flip one of the '1' bit in xxx...xxx whereas a(n) leaves xxx...xxx unchanged. Thus n-b(n) > a(n)-n. Otherwise a(n) and b(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.

In particular, this proof shows that c(n) = a(n) if n is odd and c(n) = b(n) if n is even. It also shows that a tie never occurs in determining c(n), i.e. a(n)-n is not equal to n-b(n) for all n>0.

In The On-Line Encyclopedia of Integer Sequences (OEIS), a(n) is given by sequence A057168, b(n) is given by A243109 and c(n) is given by A381764.