# Problem 108: Binary Pascal Words

$$\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.