Project Euler

Sum of Products

Given a sequence {x_1, x_2,..., x_n} of positive integers, the k -th elementary symmetric polynomial is: e_k(x_1,..., x_n) = sum_(1 <= i_1 < i_2 <... < i_k <= n) x_(i_1) x_(i_2)... x_(i_k). Compute...

Source sync Apr 19, 2026

Problem #0840

Level Level 24

Solved By 465

Languages C++, Python

Answer 194396971

Length 267 words

modular_arithmeticlinear_algebraanalytic_math

A partition of $n$ is a set of positive integers for which the sum equals $n$.

The partitions of 5 are: $\{5\},\{1,4\},\{2,3\},\{1,1,3\},\{1,2,2\},\{1,1,1,2\}$ and $\{1,1,1,1,1\}$.

Further we define the function $D(p)$ as:

$$ \begin{cases} D(1) = 1 \\ D(p) = 1 \text{, for any prime } p \\ D(pq) = D(p)q + pD(q) \text{, for any positive integers } p, q > 1 \end{cases} $$

Now let $\{a_1, a_2,\ldots,a_k\}$ be a partition of $n$.

We assign to this particular partition the value: $$P=\prod_{j=1}^{k}D(a_j)$$

$G(n)$ is the sum of $P$ for all partitions of $n$.

We can verify that $G(10) = 164$.

We also define: $$S(N)=\sum_{n=1}^{N}G(n).$$ You are given $S(10)=396$.

Find $S(5\times 10^4) \mod 999676999$.

Problem 840: Sum of Products

Mathematical Foundation

Theorem 1 (Product-Sum Identity). For any elements $x_1, \ldots, x_n$ in a commutative ring,

\sum_{k=0}^{n} e_k(x_1, \ldots, x_n) = \prod_{i=1}^{n} (1 + x_i).

In particular, $\sum_{k=1}^{n} e_k = \prod_{i=1}^{n}(1 + x_i) - 1$ .

Proof. Expand the product $\prod_{i=1}^{n}(1 + x_i)$ . Each term in the expansion is obtained by choosing, for each factor $(1 + x_i)$ , either the summand $1$ or the summand $x_i$ . If we choose $x_i$ for exactly $k$ indices $i_1 < i_2 < \cdots < i_k$ and $1$ for the remaining $n-k$ indices, the resulting monomial is $x_{i_1} x_{i_2} \cdots x_{i_k}$ . Summing over all subsets of size $k$ gives $e_k$ , and summing over all $k$ from $0$ to $n$ gives the full product. The $k=0$ term is $e_0 = 1$ (the empty product). $\square$

Theorem 2 (Newton’s Identities). Let $p_j = \sum_{i=1}^{n} x_i^j$ denote the $j$ -th power sum. Then for $k \ge 1$ :

k \cdot e_k = \sum_{j=1}^{k} (-1)^{j-1} e_{k-j}\, p_j

with $e_0 = 1$ .

Proof. Consider the generating function $E(t) = \prod_{i=1}^{n}(1 + x_i t) = \sum_{k=0}^{n} e_k t^k$ . Taking the logarithmic derivative:

\frac{E'(t)}{E(t)} = \sum_{i=1}^{n} \frac{x_i}{1 + x_i t} = \sum_{i=1}^{n} \sum_{j=0}^{\infty} (-1)^j x_i^{j+1} t^j = \sum_{j=0}^{\infty} (-1)^j p_{j+1} t^j.

Therefore $E'(t) = E(t) \cdot \sum_{j=0}^{\infty} (-1)^j p_{j+1} t^j$ . Comparing the coefficient of $t^{k-1}$ on both sides: the left side gives $k \cdot e_k$ , and the right side gives $\sum_{j=0}^{k-1} (-1)^j e_{k-1-j} p_{j+1} = \sum_{j=1}^{k} (-1)^{j-1} e_{k-j} p_j$ . $\square$

Lemma (Fundamental Theorem of Symmetric Polynomials). The ring of symmetric polynomials in $x_1, \ldots, x_n$ over $\mathbb{Z}$ is freely generated by $e_1, \ldots, e_n$ :

\mathbb{Z}[x_1, \ldots, x_n]^{S_n} = \mathbb{Z}[e_1, \ldots, e_n].

Proof. We proceed by induction on the degree of a symmetric polynomial $f$ . Order monomials lexicographically. The leading monomial of $f$ has the form $x_1^{\lambda_1} x_2^{\lambda_2} \cdots x_n^{\lambda_n}$ with $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n$ (by symmetry, the leading term must correspond to a partition). The monomial $e_1^{a_1} \cdots e_n^{a_n}$ with $a_j = \lambda_j - \lambda_{j+1}$ (setting $\lambda_{n+1} = 0$ ) has the same leading term as $f$ . Subtracting reduces the degree, and the induction proceeds. Freeness follows because the leading terms of distinct products $e_1^{a_1}\cdots e_n^{a_n}$ are distinct. $\square$

Editorial

Compute sum of all elementary symmetric polynomials e_1 + e_2 + … + e_n. Key insight: sum = prod(1 + x_i) - 1. We using Theorem 1: sum of all e_k = product(1 + x_i) - 1.

Pseudocode

    Using Theorem 1: sum of all e_k = product(1 + x_i) - 1
    result = 1
    For i from 1 to n:
        result = result * (1 + x[i]) mod p
    Return (result - 1) mod p

Complexity Analysis

Time: $O(n)$ — one modular multiplication per element.
Space: $O(1)$ auxiliary (beyond storing the input).

Answer

\boxed{194396971}

C++ project_euler/problem_840/solution.cpp

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

/*
 * Problem 840: Sum of Products
 *
 * Compute sum_{k=1}^{n} e_k(x_1,...,x_n) mod p.
 * Key: sum = prod(1 + x_i) - 1.
 *
 * Also implements Newton's identities for verification.
 */

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod; exp >>= 1;
    }
    return result;
}

// Method 1: Product formula
long long solve_product(const vector<long long>& xs) {
    long long result = 1;
    for (long long x : xs)
        result = result % MOD * ((1 + x) % MOD) % MOD;
    return (result - 1 + MOD) % MOD;
}

// Method 2: Newton's identities (for small n verification)
long long solve_newton(const vector<long long>& xs) {
    int n = xs.size();
    vector<long long> p(n + 1, 0), e(n + 1, 0);
    e[0] = 1;
    for (int j = 1; j <= n; j++)
        for (long long x : xs)
            p[j] = (p[j] + power(x, j, MOD)) % MOD;
    for (int k = 1; k <= n; k++) {
        long long s = 0;
        for (int j = 1; j <= k; j++) {
            long long term = e[k - j] * p[j] % MOD;
            if (j % 2 == 1) s = (s + term) % MOD;
            else s = (s - term + MOD) % MOD;
        }
        e[k] = s % MOD * power(k, MOD - 2, MOD) % MOD;
    }
    long long total = 0;
    for (int k = 1; k <= n; k++)
        total = (total + e[k]) % MOD;
    return total;
}

int main() {
    // Verify small cases
    vector<long long> test1 = {1, 2, 3};
    assert(solve_product(test1) == 23);
    assert(solve_newton(test1) == 23);

    vector<long long> test2 = {1, 2, 3, 4};
    assert(solve_product(test2) == 119);

    // Cross-check both methods
    vector<long long> test3 = {2, 3, 5, 7, 11};
    assert(solve_product(test3) == solve_newton(test3));

    // Solve main problem: x = (1, 2, ..., 1000)
    vector<long long> xs(1000);
    iota(xs.begin(), xs.end(), 1);
    cout << solve_product(xs) << endl;
    return 0;
}

Python project_euler/problem_840/solution.py

"""
Problem 840: Sum of Products

Compute sum of all elementary symmetric polynomials e_1 + e_2 + ... + e_n.
Key insight: sum = prod(1 + x_i) - 1.
"""

from math import comb

MOD = 10**9 + 7

# --- Method 1: Product formula (optimal) ---
def sum_esp_product(xs, mod=None):
    """sum_{k=1}^{n} e_k = prod(1 + x_i) - 1."""
    result = 1
    for x in xs:
        if mod:
            result = result * ((1 + x) % mod) % mod
        else:
            result *= (1 + x)
    return (result - 1) % mod if mod else result - 1

# --- Method 2: Newton's identities ---
def sum_esp_newton(xs):
    """Compute e_k via Newton's identities, then sum."""
    n = len(xs)
    # Power sums
    p = [0] * (n + 1)
    for j in range(1, n + 1):
        p[j] = sum(x**j for x in xs)
    # Newton recurrence
    e = [0] * (n + 1)
    e[0] = 1
    for k in range(1, n + 1):
        s = 0
        for j in range(1, k + 1):
            s += (-1)**(j - 1) * e[k - j] * p[j]
        e[k] = s // k
    return sum(e[1:])

# --- Method 3: Direct enumeration (brute force) ---
def sum_esp_brute(xs):
    """Enumerate all subsets."""
    from itertools import combinations
    n = len(xs)
    total = 0
    for k in range(1, n + 1):
        for subset in combinations(xs, k):
            prod = 1
            for v in subset:
                prod *= v
            total += prod
    return total

# --- Verification ---
test_cases = [
    [1],
    [1, 2],
    [1, 2, 3],
    [1, 2, 3, 4],
    [2, 3, 5],
    [1, 1, 1, 1, 1],
    [7, 11, 13],
]

for xs in test_cases:
    a = sum_esp_product(xs)
    b = sum_esp_newton(xs)
    c = sum_esp_brute(xs)
    assert a == b == c, f"Mismatch for {xs}: prod={a}, newton={b}, brute={c}"

print("All verification passed!")

# Compute for a larger input
xs_large = list(range(1, 1001))
answer = sum_esp_product(xs_large, MOD)
print(f"Answer: {answer}")