Problem 704

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 \leq m \leq n$ . $F (10) = 3$ and $F (100) = 6$ .

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

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

二项式系数中的质因数二

记 $g (n, m)$ 为使得 $2^{k}$ 整除 $(\binom{n}{m})$ 的最大整数 $k$ 。例如， $(\binom{12}{5}) = 792 = 2^{3} \cdot 3^{2} \cdot 11$ ，因此 $g (12, 5) = 3$ 。再定义 $F (n) = max g (n, m) : 0 \leq m \leq n$ 。已知 $F (10) = 3$ ， $F (100) = 6$ 。

记 $S (N)$ = $\sum_{n = 1}^{N} F (n)$ 。已知 $S (100) = 389$ ， $S (10^{7}) = 203222840$ 。

求 $S (10^{16})$ 。