Project Euler

Summation of Summations

Define the m -fold iterated partial sum of a sequence (a_1, a_2,..., a_n) by S^((m))_n = sum_(i_1=1)^n sum_(i_2=1)^(i_1)... sum_(i_m=1)^i_(m-1) a_(i_m). Find a closed-form expression for S^((m))_n...

Source sync Apr 19, 2026

Problem #0894

Level Level 27

Solved By 376

Languages C++, Python

Answer 0.7718678168

Length 239 words

linear_algebrasequencecombinatorics

Consider a unit circle $C_0$ on the plane that does not enclose the origin. For $k \geq 1$, a circle $C_k$ is created by scaling and rotating $C_{k - 1}$ with respect to the origin. That is, both the radius and the distance to the origin are scaled by the same factor, and the centre of rotation is the origin. The scaling factor is positive and strictly less than one. Both it and the rotation angle remain constant for each $k$.

It is given that $C_0$ is externally tangent to $C_1$, $C_7$ and $C_8$, as shown in the diagram belowm, and no two circles overlap.

Find the total area of all the circular triangles in the diagram, i.e. the are painted green above.

Give your answer rounded to $10$ places after the decimal point.

Problem 894: Summation of Summations

Mathematical Foundation

Theorem 1 (Hockey Stick / Stars-and-Bars Reduction). For any sequence $(a_k)$ and integers $m \geq 1$ , $n \geq 1$ :

S^{(m)}_n = \sum_{k=1}^{n} \binom{n - k + m - 1}{m - 1}\, a_k.

Proof. The element $a_k$ appears in $S^{(m)}_n$ once for each weakly increasing chain $k \leq i_m \leq i_{m-1} \leq \cdots \leq i_1 \leq n$ . Setting $j_\ell = i_\ell - k$ for $\ell = m$ and $j_\ell = i_\ell - i_{\ell+1}$ for $\ell < m$ , we obtain nonneg integers $j_1, \ldots, j_{m-1} \geq 0$ with the constraint $j_1 + j_2 + \cdots + j_{m-1} + (i_1 - i_1) \leq n - k$ . More precisely, the chain is equivalent to choosing $m - 1$ nonneg integers summing to at most $n - k$ , which by a standard stars-and-bars argument yields

\binom{(n - k) + (m - 1)}{m - 1} = \binom{n - k + m - 1}{m - 1}

chains. $\square$

Theorem 2 (Matrix Formulation). Let $L$ be the $n \times n$ lower-triangular matrix with $L_{ij} = [i \geq j]$ . Then $S^{(m)}_n = (L^m \mathbf{a})_n$ , and $(L^m)_{ij} = \binom{i - j + m - 1}{m - 1}$ for $i \geq j$ .

Proof. We proceed by induction on $m$ . For $m = 1$ , $(L\mathbf{a})_i = \sum_{j=1}^{i} a_j = S^{(1)}_i$ and $(L^1)_{ij} = [i \geq j] = \binom{i-j}{0}$ . Assuming $(L^m)_{ij} = \binom{i-j+m-1}{m-1}$ , we compute

(L^{m+1})_{ij} = \sum_{\ell=j}^{i} (L)_{i\ell} \cdot (L^m)_{\ell j} = \sum_{\ell=j}^{i} \binom{\ell - j + m - 1}{m - 1} = \binom{i - j + m}{m},

where the last step applies the hockey stick identity $\sum_{r=0}^{s}\binom{r+m-1}{m-1} = \binom{s+m}{m}$ . $\square$

Lemma (Special Cases).

For $a_k = 1$ : $S^{(m)}_n = \binom{n+m-1}{m}$ .
For $a_k = k$ : $S^{(m)}_n = \binom{n+m}{m+1}$ .

Proof. For $a_k = 1$ : $S^{(m)}_n = \sum_{k=1}^{n}\binom{n-k+m-1}{m-1} = \sum_{j=0}^{n-1}\binom{j+m-1}{m-1} = \binom{n+m-1}{m}$ by the hockey stick identity.

For $a_k = k$ : $S^{(m)}_n = \sum_{k=1}^{n} k\binom{n-k+m-1}{m-1}$ . Using the identity $k\binom{n-k+m-1}{m-1} = n\binom{n-k+m-1}{m-1} - (n-k)\binom{n-k+m-1}{m-1}$ and the absorption identity $(n-k)\binom{n-k+m-1}{m-1} = m\binom{n-k+m-1}{m}$ … Alternatively, note that $S^{(1)}_n = n(n+1)/2 = \binom{n+1}{2}$ for $a_k = k$ , and applying $L$ repeatedly, $S^{(m)}_n = \binom{n+m}{m+1}$ follows by induction using the hockey stick identity. $\square$

Editorial

m-fold iterated partial sum: S^(m)_n = sum_k C(n-k+m-1, m-1) * a_k Special case a_k = k: S^(m)_n = C(n+m, m+1). We o(n) computation using Theorem 1. We then compute binomial coefficients incrementally. Finally, update: binom(n-k+m-1, m-1) -> binom(n-(k-1)+m-1, m-1).

Pseudocode

O(n) computation using Theorem 1
Compute binomial coefficients incrementally
Update: binom(n-k+m-1, m-1) -> binom(n-(k-1)+m-1, m-1)
O(mn) computation via m passes of prefix sums

Complexity Analysis

Time (closed-form method): $O(n)$ — single pass with incremental binomial coefficient updates.
Space (closed-form method): $O(1)$ beyond the input array.
Time (prefix sum method): $O(mn)$ — $m$ passes of prefix summation.
Space (prefix sum method): $O(n)$ for the working array.
Time (naive nested loops): $O(n^m)$ .
Space (naive nested loops): $O(1)$ .

Answer

\boxed{0.7718678168}

C++ project_euler/problem_894/solution.cpp

/*
 * Problem 894: Summation of Summations
 * m-fold iterated partial sum: S^(m)_n = sum_k C(n-k+m-1, m-1) * a_k.
 * For a_k = k: S^(m)_n = C(n+m, m+1).
 * Three approaches: nested loops O(n^m), prefix sums O(mn), closed form O(n).
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll comb(ll n, ll r) {
    if (r < 0 || r > n) return 0;
    if (r > n - r) r = n - r;
    ll result = 1;
    for (ll i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

// Method 1: Direct nested loops for m=3
ll triple_sum_brute(const vector<ll>& a) {
    int n = a.size();
    ll total = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            for (int k = 0; k <= j; k++)
                total += a[k];
    return total;
}

// Method 2: Prefix sum applied m times
ll iterated_prefix(vector<ll> a, int m) {
    int n = a.size();
    for (int step = 0; step < m; step++)
        for (int i = 1; i < n; i++)
            a[i] += a[i - 1];
    return a[n - 1];
}

// Method 3: Closed-form weighted sum
ll closed_form(const vector<ll>& a, int m) {
    int n = a.size();
    ll total = 0;
    for (int k = 0; k < n; k++) {
        ll weight = comb(n - 1 - k + m - 1, m - 1);
        total += weight * a[k];
    }
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Verification: a_k = k, m = 3
    cout << "=== Triple Summation (m=3, a_k=k) ===" << endl;
    for (int n = 1; n <= 10; n++) {
        vector<ll> a(n);
        for (int i = 0; i < n; i++) a[i] = i + 1;
        ll b = triple_sum_brute(a);
        ll p = iterated_prefix(a, 3);
        ll c = closed_form(a, 3);
        ll identity = comb(n + 3, 4);
        cout << "n=" << setw(2) << n
             << ": brute=" << setw(6) << b
             << " prefix=" << setw(6) << p
             << " formula=" << setw(6) << c
             << " C(n+3,4)=" << setw(6) << identity
             << (b == p && p == c && c == identity ? " OK" : " FAIL") << endl;
        assert(b == p && p == c && c == identity);
    }

    // General m verification
    cout << "\n=== Various m (a_k=k, n=10) ===" << endl;
    int n = 10;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) a[i] = i + 1;
    for (int m = 1; m <= 6; m++) {
        ll prefix = iterated_prefix(a, m);
        ll formula = closed_form(a, m);
        ll identity = comb(n + m, m + 1);
        cout << "m=" << m << ": prefix=" << prefix
             << " formula=" << formula
             << " C(n+m,m+1)=" << identity
             << (prefix == formula && formula == identity ? " OK" : " FAIL") << endl;
    }

    // Large computation
    ll ans = comb(10003, 4);
    cout << "\nS^(3)_{10000} for a_k=k = C(10003,4) = " << ans << endl;
    cout << "\nAnswer: " << ans << endl;

    return 0;
}

Python project_euler/problem_894/solution.py

"""
Problem 894: Summation of Summations
m-fold iterated partial sum: S^(m)_n = sum_k C(n-k+m-1, m-1) * a_k
Special case a_k = k: S^(m)_n = C(n+m, m+1).
"""

from math import comb

def iterated_sum_brute(a, m):
    """Compute m-fold iterated partial sum by nested iteration."""
    n = len(a)
    current = list(a)
    for _ in range(m):
        prefix = [0] * n
        prefix[0] = current[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + current[i]
        current = prefix
    return current[-1]

def iterated_sum_formula(a, m):
    """Compute using closed-form: sum_k C(n-k+m-1, m-1) * a_k."""
    n = len(a)
    total = 0
    for k in range(n):
        weight = comb(n - 1 - k + m - 1, m - 1)
        total += weight * a[k]
    return total

def iterated_sum_prefix(a, m):
    """Compute by applying prefix sum m times. O(mn)."""
    current = list(a)
    for _ in range(m):
        for i in range(1, len(current)):
            current[i] += current[i - 1]
    return current[-1]

def iterated_sum_identity(n, m):
    """For a_k = k: S^(m)_n = C(n+m, m+1)."""
    return comb(n + m, m + 1)

# --- Verification ---
print("=== Triple Summation (m=3) Verification ===")
for n in range(1, 11):
    a = list(range(1, n + 1))  # a_k = k
    brute = iterated_sum_brute(a, 3)
    formula = iterated_sum_formula(a, 3)
    prefix = iterated_sum_prefix(a, 3)
    identity = iterated_sum_identity(n, 3)
    match = "OK" if brute == formula == prefix == identity else "FAIL"
    print(f"  n={n:>2}: brute={brute:>6}, formula={formula:>6}, "
          f"prefix={prefix:>6}, C(n+3,4)={identity:>6}  {match}")
    assert brute == formula == prefix == identity

print("\n=== a_k = 1 (m=2) ===")
for n in range(1, 11):
    a = [1] * n
    result = iterated_sum_formula(a, 2)
    expected = comb(n + 1, 2)
    print(f"  n={n}: S^(2) = {result}, C(n+1,2) = {expected}, "
          f"Match: {'OK' if result == expected else 'FAIL'}")
    assert result == expected

print("\n=== General sequence verification ===")
a = [3, 1, 4, 1, 5, 9, 2, 6]
for m in range(1, 6):
    brute = iterated_sum_brute(a, m)
    formula = iterated_sum_formula(a, m)
    prefix = iterated_sum_prefix(a, m)
    print(f"  m={m}: brute={brute}, formula={formula}, prefix={prefix}, "
          f"Match: {'OK' if brute == formula == prefix else 'FAIL'}")
    assert brute == formula == prefix

print("\n=== Weight Table (m=3, n=5) ===")
n = 5
print(f"{'k':>3} {'C(n-k+2,2)':>12} {'Contribution (a_k=k)':>22}")
for k in range(1, n + 1):
    w = comb(n - k + 2, 2)
    print(f"{k:>3} {w:>12} {w * k:>22}")

# Large computation
n_large = 10000
m_large = 3
a_large = list(range(1, n_large + 1))
result = iterated_sum_identity(n_large, m_large)
print(f"\nS^(3)_{{10000}} for a_k=k: C(10003, 4) = {result}")

answer = result
print(f"\nAnswer: {answer}")

# --- 4-Panel Visualization ---