Factors of Two in Binomial Coefficients

Define $g(n, m)$ to be the largest integer $k$ such that $2^k$ divides $\binom{n}m$.
For example, $\binom{12}5 = 792 = 2^3 \cdot 3^2 \cdot 11$, hence $g(12, 5) = 3$.
Then define $F(n) = \max \{ g(n, m) : 0 \le m \le n \}$. $F(10) = 3$ and $F(100) = 6$.

Let $S(N)$ = $\displaystyle\sum_{n=1}^N{F(n)}$. You are given that $S(100) = 389$ and $S(10^7) = 203222840$.

Find $S(10^{16})$.

This is a difficult combinatorics problem often seen in mathematics competitions or in advanced problem sets. It makes use of concepts such as binomial coefficients and the valuation of a factor in a number.

First, let’s define $v_2(n)$ as the highest power of 2 that divides n.

Given the equation $g(n, m) = v_2(\binom{n}{m})$, it will reach its maximum when m is as close to $\frac{n}{2}$ as possible, because that’s when $\binom{n}{m}$ is at its maximum. If n is even, m will be $\frac{n}{2}$, but if n is odd, m will be either $\frac{n-1}{2}$ or $\frac{n+1}{2}$.

Given our new equation $F(n) = v_2(\binom{n}{\lfloor \frac{n}{2} \rfloor})$, we can use Legendre’s Formula, which states that the highest power of a prime p that divides n! is given by $\frac{n – s_p(n)}{p-1}$, where $s_p(n)$ is the sum of the digits of n in base p.

Using Legendre’s formula, we find that the $v_2(n!) = n – s_2(n)$.

Applying this to the binomial coefficient, we find that $v_2(\binom{n}{m}) = [n – s_2(n)] – 2[m – s_2(m)]$. This is equal to $s_2(m) – n + 2m$, or rearranged to $s_2(m) + m = n + s_2(n)$.

$p = m + s_2(m)$ will accept positive integers m that are between $0$ and $n$, which implies that $m = p\ mod \ 2^k$ and $2^k \leq n$, where k is the $k$th value such that $2^k$ divides $\binom{n}{m}$.

The sum of the maximum k for all values of n up to N is given by $S(n) = \sum_{k=1}^{\infty} ks_k(n)$, where $s_k(n) = \lfloor \frac{n}{2^k} \rfloor$.

Unfortunately, this is as far as conventional mathematical methods can bring us. The remainder of this problem is best solved using a computer to calculate the remaining values. It involves iterating each possible n value up to our target, 10^16, finding the maximum k for that n, and adding that to a running total.

This problem is a typical example of the sorts of problems that are outlined using mathematical theory but require computational methods to reach the final answer due to the numbers involved being too large to feasibly calculate by hand.

More Answers: