CLR cover
Previous problem

Problem 108: Binary Pascal Words

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

Pascal's triangle displays binomial coefficients following Pascal's rule: $$\binom{n}{i}=\binom{n-1}{i-1}+\binom{n-1}{i}.$$ The regular structure of the triangle permits fast access to coefficients. In the problem, the $n$th binary Pascal word $P_n$ is the $n$th row of Pascal's triangle modulo 2, that is, for $0\leq i\leq n$: $$P_n[i] = \binom{n}{i} \bmod 2.$$ Here are the resulting words $P_n$ for $0\leq n\leq 6$:
$P_{0}$=$\sa{1}$
$P_{1}$=$\sa{1}$$\sa{1}$
$P_{2}$=$\sa{1}$$\sa{0}$$\sa{1}$
$P_{3}$=$\sa{1}$$\sa{1}$$\sa{1}$$\sa{1}$
$P_{4}$=$\sa{1}$$\sa{0}$$\sa{0}$$\sa{0}$$\sa{1}$
$P_{5}$=$\sa{1}$$\sa{1}$$\sa{0}$$\sa{0}$$\sa{1}$$\sa{1}$
$P_{6}$=$\sa{1}$$\sa{0}$$\sa{1}$$\sa{0}$$\sa{1}$$\sa{0}$$\sa{1}$

Given the binary representations $r_kr_{k - 1}\cdots r_0$ of $n$ and $c_kc_{k - 1}\cdots c_0$ of $i$, show how to compute in time $O(k)$ the letter $P_n[i]$ and the number of occurrences of $\sa{1}$ in $P_n$.
Possibly use Lucas's Theorem.

Theorem [Lucas, 1852]

If $p$ is a prime number and $r_kr_{k - 1}\cdots r_0$, $c_kc_{k - 1}\cdots c_0$ are the based $p$ representations of the respective integers $r$ and $c$ with $r\geq c\geq 0$, then $$\binom{r}{c}\bmod p = \prod_{i = 0}^k \binom{r_i}{c_i} \bmod p.$$

References

  • N. J. Fine. Binomial coefficients modulo a prime. The American Mathematical Monthly, 54(10, Part 1):589-592, December 1947.