Project Euler Problem 704

Solution

Answer: 501985601490518144

Using Kummer's theorem:

$$g(n,m)=v_2!\binom{n}{m}$$

equals the number of carries when adding $m$ and $n-m$ in binary.

The maximum possible number of carries occurs when we force carries through the longest possible suffix of 1s in $n$. This gives

$$F(n)=\lfloor \log_2 n \rfloor - v_2(n+1) + \mathbf 1_{,n+1\text{ is a power of }2}.$$

Equivalently:

if $n\neq 2^k-1$,

$$F(n)=\lfloor \log_2 n \rfloor-v_2(n+1),$$

and $F(2^k-1)=0$.

Therefore

$$S(N)=\sum_{n=1}^N \lfloor \log_2 n \rfloor -\sum_{n=1}^N v_2(n+1) +#{k:2^k-1\le N}.$$

Now compute each term.

1. Sum of floor logarithms

Let $L=\lfloor \log_2 N\rfloor$.

$$\sum_{n=1}^N \lfloor \log_2 n \rfloor = \sum_{k=0}^{L-1} k,2^k +L(N-2^L+1).$$

Using

$$\sum_{k=0}^{L-1} k2^k=(L-2)2^L+2,$$

we get

$$A=(L-2)2^L+2+L(N-2^L+1).$$

2. Sum of $v_2(n+1)$

$$\sum_{n=1}^N v_2(n+1) = \sum_{m=2}^{N+1} v_2(m) = v_2((N+1)!).$$

By Legendre's formula,

$$v_2((N+1)!)=(N+1)-s_2(N+1),$$

where $s_2(x)$ is the binary digit sum.

$$B=(N+1)-s_2(N+1).$$

3. Count of Mersenne numbers

$$C=\left\lfloor \log_2(N+1)\right\rfloor.$$

For $N=10^{16}$:

$L=\lfloor \log_2(10^{16})\rfloor=53$,
$s_2(10^{16}+1)=27$.

Substituting:

$$S(10^{16}) = 501985601490518144.$$

A compact Python implementation is:

def S(N):
    L = N.bit_length() - 1

    A = ((L - 2) << L) + 2 + L * (N - (1 << L) + 1)
    B = (N + 1) - bin(N + 1).count("1")
    C = (N + 1).bit_length() - 1

    return A - B + C

print(S(10**16))

This also reproduces the given checks:

$S(100)=389$
$S(10^7)=203222840$

so the derivation is consistent.

Answer: 501985601490518144