Project Euler

Counting Block Combinations II

A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least on...

Source sync Apr 19, 2026

Problem #0115

Level Level 04

Solved By 11,368

Languages C++, Python

Answer 168

Length 311 words

sequenceoptimizationalgebra

Note: This is a more difficult version of Problem 114

A row measuring $n$ units in length has red blocks with a minimum length of $m$ units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.

Let the fill-count function, $F(m, n)$, represent the number of ways that a row can be filled.

For example, $F(3, 29) = 673135$ and $F(3, 30) = 1089155$.

That is, for $m = 3$, it can be seen that $n = 30$ is the smallest value for which the fill-count function first exceeds one million.

In the same way, for $m = 10$, it can be verified that $F(10, 56) = 880711$ and $F(10, 57) = 1148904$, so $n = 57$ is the least value for which the fill-count function first exceeds one million.

For $m = 50$, find the least value of $n$ for which the fill-count function first exceeds one million.

Problem 115: Counting Block Combinations II

Mathematical Foundation

Theorem 1 (Generalized tiling recurrence). The fill-count function satisfies:

F(m, n) = F(m, n-1) + \sum_{L=m}^{n} F(m, n - L - 1)

with base cases $F(m, -1) = 1$ and $F(m, 0) = 1$ .

Proof. The argument is identical to Problem 114, generalized from minimum block length 3 to arbitrary $m$ . The leftmost cell is either:

A black square, leaving $F(m, n-1)$ ways for the rest, or
The start of a red block of length $L \geq m$ , followed by a mandatory black separator (unless $L = n$ ), leaving $F(m, n - L - 1)$ ways.

These cases are mutually exclusive and exhaustive, and $F(m, -1) = 1$ correctly handles the boundary $L = n$ . $\square$

Lemma 1 (Prefix sum optimization). Define $P(k) = \sum_{j=-1}^{k} F(m, j)$ . Then:

F(m, n) = F(m, n-1) + P(n - m - 1)

Proof. Substituting $j = n - L - 1$ in the sum of Theorem 1, as $L$ ranges from $m$ to $n$ , $j$ ranges from $-1$ to $n - m - 1$ :

\sum_{L=m}^{n} F(m, n - L - 1) = \sum_{j=-1}^{n-m-1} F(m, j) = P(n - m - 1)

$\square$

Theorem 2 (Exponential growth). For fixed $m$ , $F(m, n)$ grows exponentially with dominant growth rate $\lambda > 1$ satisfying:

\lambda^{m+1} = \lambda^m + 1

Proof. Using the prefix-sum recurrence, we can derive that $F(m, n) - F(m, n-1) = F(m, n - m - 1)$ , which gives the $(m+1)$ -term recurrence:

F(m, n) = F(m, n-1) + F(m, n - m - 1)

The characteristic polynomial is $x^{m+1} - x^m - 1 = 0$ , which factors as $x^{m+1} = x^m + 1$ . By Descartes’ rule of signs, this polynomial has exactly one positive real root $\lambda > 1$ . By the theory of linear recurrences, $F(m, n) \sim C \cdot \lambda^n$ for some constant $C > 0$ . $\square$

Remark. The simplified recurrence $F(m,n) = F(m,n-1) + F(m,n-m-1)$ holds for $n \geq m$ , but one must be careful with initial conditions. The prefix-sum approach avoids these subtleties.

Theorem 3 (Verification). $F(3, 7) = 17$ , $F(3, 29) = 673135$ , and $F(3, 30) = 1089155$ .

Proof. Direct computation using the recurrence, verified against Problem 114 and the problem statement values. $\square$

Editorial

Recurrence: F(m, n) = F(m, n-1) + P(n-m-1) where P(k) = sum of F(m, j) for j = -1 to k. We else.

Pseudocode

    F[-1] = 1; F[0] = 1
    P[-1] = 1; P[0] = 2
    for n = 1, 2, 3, ...:
        If n >= m then
            idx = n - m - 1
            sum_term = P[idx] if idx >= -1 else 0
        else:
            sum_term = 0
        F[n] = F[n-1] + sum_term
        P[n] = P[n-1] + F[n]
        If F[n] > target then
            Return n

Complexity Analysis

Time: $O(n^*)$ where $n^* = 168$ is the answer. Each step is $O(1)$ .
Space: $O(n^*)$ for storing $F$ and $P$ values.

Answer

\boxed{168}

C++ project_euler/problem_115/solution.cpp

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

/*
 * Problem 115: Counting Block Combinations II
 * Find least n where F(50, n) > 1,000,000.
 *
 * Recurrence: F(m, n) = F(m, n-1) + P(n-m-1)
 * where P(k) = sum of F(m, j) for j = -1..k
 *
 * Cross-checks:
 *   F(3, 7) = 17
 *   F(10, n) first exceeds 10^6 at n = 57
 */

int main() {
    const int m = 50;
    const long long target = 1000000;

    map<int, long long> f, prefix;
    f[-1] = 1; f[0] = 1;
    prefix[-1] = 1; prefix[0] = 2;

    for (int n = 1; ; n++) {
        long long p = 0;
        int idx = n - m - 1;
        if (idx >= -1 && prefix.count(idx)) {
            p = prefix[idx];
        }
        f[n] = f[n - 1] + p;
        prefix[n] = prefix[n - 1] + f[n];

        if (f[n] > target) {
            assert(n == 168);
            cout << n << endl;
            return 0;
        }
    }
}

Python project_euler/problem_115/solution.py

"""
Problem 115: Counting Block Combinations II

Find the least n for which F(50, n) > 1,000,000 where F(m, n) counts
ways to fill a row of length n with red blocks of minimum length m,
separated by at least one black square.

Recurrence: F(m, n) = F(m, n-1) + P(n-m-1)
where P(k) = sum of F(m, j) for j = -1 to k.
"""

# ---------------------------------------------------------------------------
# ---------------------------------------------------------------------------
def fill_count(m: int, target: int):
    """Find least n where F(m, n) > target. Returns (n, {n: F(m,n)})."""
    f = {-1: 1, 0: 1}
    prefix = {-1: 1, 0: 2}  # prefix[k] = sum of f[-1]..f[k]

    n = 0
    while True:
        n += 1
        p_idx = n - m - 1
        p = prefix.get(p_idx, 0) if p_idx >= -1 else 0
        f[n] = f[n - 1] + p
        prefix[n] = prefix[n - 1] + f[n]

        if f[n] > target:
            return n, f

# ---------------------------------------------------------------------------
# ---------------------------------------------------------------------------
def fill_count_brute(m: int, n: int):
    """Count valid configurations by recursion."""
    if n < 0:
        return 1 if n == -1 else 0
    if n == 0:
        return 1
    # Place black at position n
    count = fill_count_brute(m, n - 1)
    # Place red block of length L ending at position n
    for L in range(m, n + 1):
        count += fill_count_brute(m, n - L - 1)
    return count

# ---------------------------------------------------------------------------
# Verify and solve
# ---------------------------------------------------------------------------
# Cross-check with brute force for small cases
for n_test in range(15):
    assert fill_count_brute(3, n_test) == fill_count(3, 10**18)[1].get(n_test, 1), \
        f"Mismatch at F(3, {n_test})"

# Verify known values
_, f3 = fill_count(3, 10**18)
assert f3[7] == 17, f"F(3,7) should be 17, got {f3[7]}"

# Verify F(10, n) first exceeds 10^6 at n=57
n10, _ = fill_count(10, 1_000_000)
assert n10 == 57, f"F(10, n) exceeds 10^6 at n={n10}, expected 57"

# Main computation
answer, f50 = fill_count(50, 1_000_000)
assert answer == 168, f"Expected 168, got {answer}"
print(answer)

# ---------------------------------------------------------------------------
# 4-Panel Visualization
# ---------------------------------------------------------------------------