Problem 704: Factors of Two in Binomial Coefficients

Mathematical Foundation

Theorem 1 (Kummer, 1852). The $p$-adic valuation $\nu_p\binom{n}{m}$ equals the number of carries when adding $m$ and $n - m$ in base $p$.

Proof. By Legendre’s formula, $\nu_p(k!) = \sum_{i=1}^{\infty}\lfloor k/p^i \rfloor$. Therefore

Each summand equals the carry out of position $i-1$ when adding $m$ and $n-m$ in base $p$. This is Kummer’s classical result. $\square$

Theorem 2 (Maximum 2-adic Valuation). For $n \ge 1$,

where $\nu_2(n)$ is the 2-adic valuation of $n$ (the exponent of 2 in the factorization of $n$).

Proof. Write $n$ in binary as $n = (b_L b_{L-1} \cdots b_1 b_0)_2$ where $b_L = 1$ and $L = \lfloor \log_2 n \rfloor$. Let $\nu_2(n) = t$, so bits $b_0 = b_1 = \cdots = b_{t-1} = 0$ and $b_t = 1$.

By Kummer’s theorem, $\nu_2\binom{n}{m}$ counts the carries in $m + (n-m)$ in binary. A carry at position $i$ occurs when $m_i + (n-m)_i + c_{i-1} \ge 2$, where $c_{i-1}$ is the incoming carry.

Upper bound: The total number of carries is at most $L - t$. Position $t$ is the lowest 1-bit of $n$. At positions $0, 1, \ldots, t-1$, we have $n_i = 0$, so $m_i + (n-m)_i = m_i + (n-m)_i$ must produce digit $0$. If there is an incoming carry, the outgoing carry simply propagates but does not create a “net” carry. The bit at position $L$ is the highest bit and cannot generate a carry out. Hence at most $L - t$ positions can contribute carries.

Achievability: Choose $m$ such that in binary addition $m + (n-m)$, carries are generated at every position from $t$ through $L-1$. For example, take $m = (0 \, b_{L-1} \, b_{L-2} \cdots b_{t+1} \, 0 \, \underbrace{1 \cdots 1}_{t})_2$ (a specific construction that maximizes carry chain length). This produces exactly $L - t$ carries. $\square$

Lemma 1 (Summation Decomposition). $S(N) = A(N) - B(N)$, where

Proof. Immediate from $F(n) = \lfloor \log_2 n \rfloor - \nu_2(n)$ and linearity of summation. $\square$

Lemma 2 (Closed Form for $A(N)$). Let $L = \lfloor \log_2 N \rfloor$. Then

Proof. For $b = 0, 1, \ldots, L-1$, the integers $n$ with $\lfloor \log_2 n \rfloor = b$ are $\{2^b, 2^b + 1, \ldots, 2^{b+1} - 1\}$, contributing $b \cdot 2^b$. The remaining integers $\{2^L, \ldots, N\}$ contribute $L(N - 2^L + 1)$. Thus:

The identity $\sum_{b=0}^{L-1} b \cdot 2^b = (L-2)\cdot 2^L + 2$ follows by differentiating the geometric series $\sum x^b$ and substituting $x = 2$. $\square$

Lemma 3 (Closed Form for $B(N)$).

Proof. Each integer $n$ contributes $\nu_2(n)$ to $B(N)$. The value $\nu_2(n) \ge k$ iff $2^k \mid n$, so $B(N) = \sum_{k=1}^{\infty} \lfloor N/2^k \rfloor$, which terminates at $k = L$. $\square$

Editorial

We compute A(N). Finally, compute B(N). We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

Compute A(N)
Compute B(N)

Complexity Analysis

• Time: $O(\log N)$, since the loop runs $L = \lfloor \log_2 N \rfloor$ iterations and all arithmetic is $O(1)$ (with big-integer support for $N = 10^{16}$).
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 lll;

int main() {
    ll N = 10000000000000000LL; // 10^16

    // S(N) = sum_{n=1}^{N} F(n)
    // F(n) = floor(log2(n)) - v2(n)
    // S(N) = A(N) - B(N)
    // A(N) = sum of floor(log2(n)) for n=1..N
    // B(N) = sum of v2(n) for n=1..N

    // Compute A(N) = sum of floor(log2(n)) for n=1..N
    int B = 63 - __builtin_clzll(N); // floor(log2(N))
    // sum_{b=0}^{B-1} b * 2^b = (B-2)*2^B + 2
    // Plus B * (N - 2^B + 1) for numbers from 2^B to N

    // Use __int128 to avoid overflow
    lll powerB = (lll)1 << B;
    lll A = (lll)(B - 2) * powerB + 2 + (lll)B * ((lll)N - powerB + 1);

    // Compute B(N) = sum_{k=1}^{inf} floor(N/2^k)
    lll Bval = 0;
    for (int k = 1; k <= B; k++) {
        Bval += (lll)N >> k;
    }

    lll result = A - Bval;

    // Print __int128
    ll r = (ll)result;
    cout << r << endl;

    return 0;
}

#!/usr/bin/env python3
"""Project Euler Problem 704: Factors of Two in Binomial Coefficients"""

def solve():
    N = 10**16

    # F(n) = floor(log2(n)) - v2(n) where v2(n) is 2-adic valuation
    # S(N) = sum F(n) for n=1..N = A(N) - B(N)

    # A(N) = sum of floor(log2(n)) for n=1..N
    B = N.bit_length() - 1  # floor(log2(N))
    powerB = 1 << B
    # sum_{b=0}^{B-1} b * 2^b = (B-2)*2^B + 2
    A = (B - 2) * powerB + 2 + B * (N - powerB + 1)

    # B(N) = sum of v2(n) for n=1..N = sum_{k>=1} floor(N/2^k)
    Bval = 0
    for k in range(1, B + 1):
        Bval += N >> k

    result = A - Bval
    print(result)

    # Verify with small cases
    def F(n):
        if n == 0:
            return 0
        return (n.bit_length() - 1) - (n & -n).bit_length() + 1

    def S_brute(N):
        return sum(F(n) for n in range(1, N + 1))

    # Check S(100)
    print(f"S(100) = {S_brute(100)} (expected 389)")
    print(f"S(10^7) check with formula:")

    # Formula check for N=100
    B100 = 99 .bit_length() - 1  # Actually need bit_length of 100
    B100 = (100).bit_length() - 1
    p100 = 1 << B100
    A100 = (B100 - 2) * p100 + 2 + B100 * (100 - p100 + 1)
    Bval100 = sum(100 >> k for k in range(1, B100 + 1))
    print(f"Formula S(100) = {A100 - Bval100} (expected 389)")

solve()