Problem 115: Counting Block Combinations II

Project Euler Problem 115 Solution

EulerSolve provides an optimized solution for Project Euler Problem 115, Counting Block Combinations II, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $F(m,n)$ be the number of ways to fill a row of length $n$ with black squares and red blocks of length at least $m$, under the rule that any two red blocks must be separated by at least one black square. The all-black row is allowed and must be counted. Problem 115 fixes $m=50$ and asks for the smallest row length $n$ such that $F(50,n) \gt 1{,}000{,}000$. This is the same fill-count function that appears in the previous problem, but the role of $n$ changes: instead of evaluating one fixed row length, we must understand how the count grows and detect the first row where it crosses the threshold. Mathematical Approach Write $F_m(n)=F(m,n)$. The key is to count arrangements by looking at what happens at the left end of the row. That point of view leads directly to the recurrence used by the implementations. The Fill-Count Function If $0 \le n \lt m$, no red block fits at all, so the only legal arrangement is the all-black row. Therefore $$F_m(0)=1,\qquad F_m(n)=1 \text{ for } 1 \le n \lt m.$$ Those values are the first invariant of the problem: before the row is long enough to hold a red block, the count stays at 1. A Left-End Decomposition Now assume $n \ge m$. A legal arrangement of length $n$ falls into two disjoint classes. First, the row may begin with a black square....

Detailed mathematical approach

Problem Summary

A row of $n$ unit squares is filled with red blocks and black squares. Every red block is at least $m$ units long, two blocks may have different lengths, and any two red blocks are separated by at least one black square. The fill-count function $F(m,n)$ counts the ways to fill the row, including the row without any red block. The statement gives $F(3,29)=673135$ and $F(3,30)=1089155$, so for $m=3$ the length $n=30$ is the smallest for which the count exceeds one million; in the same way $F(10,56)=880711$ and $F(10,57)=1148904$, so for $m=10$ it is $n=57$. We must find the least $n$ with $F(50,n)\gt10^6$. ^[1] It is the harder version of Problem 114, where $m=3$ and a row of seven units can be filled in seventeen ways. ^[2]

The whole solution in one sentence: a row starts either with a black square, followed by any row one square shorter, or with a red block of some length $b\ge m$ that fills the row or is followed by a black square and any row $b+1$ squares shorter, so each $F(m,n)$ is a sum of earlier values, and computing them for $n=0,1,2,\dots$ until one exceeds a million gives the answer.

Mathematical Approach

We start with rows small enough to list and build up to exact formulas.

1. Small rows by hand

Write a filled row as a word, with $\mathtt R$ for a red square and $\mathtt B$ for a black one, and take $m=3$. Rows of $0$, $1$ or $2$ squares can only be all black, so $F(3,0)=F(3,1)=F(3,2)=1$; the empty row counts once, for a reason given in Section 3. A row of $3$ squares is $\mathtt{BBB}$ or a single block $\mathtt{RRR}$, so $F(3,3)=2$. Four squares give $\mathtt{BBBB}$, $\mathtt{RRRB}$, $\mathtt{BRRR}$ and $\mathtt{RRRR}$, so $F(3,4)=4$; $\mathtt{RRRR}$ is a single block of four, because blocks never touch. Five squares give the black row, a block of three in three places ($\mathtt{RRRBB}$, $\mathtt{BRRRB}$, $\mathtt{BBRRR}$), a block of four in two places and a block of five, so $F(3,5)=1+3+2+1=7$. Two blocks need at least $3+1+3=7$ squares, and the first such row is $\mathtt{RRRBRRR}$. The counts for $n=0,1,\dots,12$ are

$1, 1, 1, 2, 4, 7, 11,$
$17, 27, 44, 72, 117, 189,$

and the value $17$ for seven squares is the count quoted in Problem 114.

2. Red runs and the brute-force count

Two red blocks never touch, so every block is a run: a stretch of neighbouring red squares with no red square just before or after it. A filling is therefore the same thing as a colouring of the $n$ squares in red and black in which every run of red squares has at least $m$ squares. For $m=1$ every colouring qualifies, so $F(1,n)=2^n$, and the first length above a million is $n=20$, because $2^{19}=524288$ and $2^{20}=1048576$.

Listing all $2^n$ colourings is a good check for short rows, but $n=30$ already means about $10^9$ of them and $n=50$ about $10^{15}$, so we must count without listing.

3. Cutting off the first square

Fix $m$ and write $F(n)$ for $F(m,n)$. Every filling of a row of $n\ge1$ squares falls into exactly one of three cases, decided by its first square and, if that square is red, by the length of its block:

the first square is black: the other $n-1$ squares form any filling of a shorter row, in $F(n-1)$ ways;
the first square starts a red block of length $b$ with $m\le b\le n-1$: the square after the block must be black, since otherwise the block would be longer, and the remaining $n-1-b$ squares form any filling, in $F(n-1-b)$ ways;
the whole row is one red block, which is possible exactly when $n\ge m$.

With $[n\ge m]$ equal to $1$ when $n\ge m$ and $0$ otherwise, this gives, for every $n\ge1$,

$$F(n)=F(n-1)+[n\ge m]+\sum_{b=m}^{n-1}F(n-1-b).$$

When a block and its black square take up the whole row, nothing remains, and there is exactly one way to fill nothing; that is why $F(0)=1$. For $n\lt m$ the sum is empty and the formula gives $F(n)=F(n-1)=1$. For $m=3$ and $n=7$ it gives $F(7)=F(6)+F(3)+F(2)$${}+F(1)+F(0)+1$${}=11+2+1+1+1+1=17$. The six terms are the $11$ rows that start with a black square; a block of $3$, $4$, $5$ or $6$ squares followed by a black square and a filling of the remaining $3$, $2$, $1$ or $0$ squares, in $2$, $1$, $1$ and $1$ ways; and the single block of $7$ squares. The row $\mathtt{RRRBRRR}$ with two blocks hides in the term $F(3)=2$: a block of three, a black square, then $\mathtt{RRR}$.

This is dynamic programming: a count is reduced to counts for shorter rows, each computed once and stored, and the table is filled from short rows to long ones, so every value on the right-hand side is ready when it is needed. ^[3] The length alone describes what is left, because the black square after a block is cut off with the block, so the rest of the row is free; had we cut off only the block, we would also have to remember that the next square must be black.

4. A recurrence with three terms

The rows of $n$ squares that end with a black square correspond one to one to the rows of $n-1$ squares, by removing or appending that last square, so $D(n)=F(n)-F(n-1)$ counts the rows of $n$ squares that end with a red square. Let $b\ge m$ be the length of the last block of such a row, and let $n\ge m+1$. If $b\gt m$, removing the last square leaves a row of $n-1$ squares that still ends with a red block, now of length $b-1\ge m$, and appending a red square undoes this; so there are $D(n-1)$ such rows. If $b=m$, the last block is preceded by a black square, and in front of that stands any filling of $n-m-1$ squares, in $F(n-m-1)$ ways. Hence $D(n)=D(n-1)+F(n-m-1)$, that is,

$$F(n)=2F(n-1)-F(n-2)+F(n-m-1)\qquad(n\ge m+1),$$

with $F(n)=1$ for $n\lt m$ and $F(m)=2$. For $m=3$: $F(7)=2\cdot11-7+F(3)$${}=22-7+2=17$. Each new value now costs three operations, whatever $m$ is, so all values up to $N$ cost $O(N)$.

5. Counting by the number of blocks

A row with $k$ red blocks is described by the block lengths $b_1,\dots,b_k\ge m$ and the lengths of the black stretches: $g_0\ge0$ before the first block, $g_1,\dots,g_{k-1}\ge1$ between the blocks and $g_k\ge0$ after the last one, which together add up to $n$. Subtract $m$ from every block length and $1$ from every inner stretch: the $2k+1$ new numbers are all at least $0$ and add up to $n-mk-(k-1)$, and every such list of numbers gives back exactly one row. By stars and bars, a whole number $s\ge0$ can be written as an ordered sum of $j$ numbers that are at least $0$ in $\binom{s+j-1}{j-1}$ ways: put $s$ stars and $j-1$ bars in a row and read off the numbers of stars between the bars. ^[4] With $s=n-mk-k+1$ and $j=2k+1$, the number of rows with $k$ blocks is $\binom{n-(m-1)k+1}{2k}$. This needs $s\ge0$, that is, at least $k(m+1)-1$ squares, so $k$ runs up to $K=\lfloor(n+1)/(m+1)\rfloor$, where $\lfloor\cdot\rfloor$ rounds down to a whole number:

$$F(m,n)=\sum_{k=0}^{K}\binom{n-(m-1)k+1}{2k}.$$

The term $k=0$ is the black row. For $m=3$ and $n=8$ the terms are $1+21+5=27$. The $21$ rows with one block are the $6+5+4+3+2+1$ positions of blocks of length $3$ to $8$. The $5$ rows with two blocks start from $\mathtt{RRRBRRR}$ and put the one spare square in front, into the first block, into the gap, into the second block or at the end: $\mathtt{BRRRBRRR}$, $\mathtt{RRRRBRRR}$, $\mathtt{RRRBBRRR}$, $\mathtt{RRRBRRRR}$ and $\mathtt{RRRBRRRB}$. For the statement's $F(10,57)$ the terms for $k=0,1,\dots,5$ are

$1+1176+91390+736281$
${}+319770+286=1148904,$

so most of these rows have three blocks. For $m\le n\le2m$ we have $K=1$, so only one block fits and $F(m,n)=1+\binom{n-m+2}{2}$. For $m=50$ this gives $F(50,50)=2$, $F(50,51)=4$ and $F(50,100)=1327$; rows with two blocks appear from $n=101$ on and rows with three from $n=152$ on, so each count is a sum of only a few binomial coefficients.

The same argument handles a stricter rule: if any two blocks must be separated by at least $d\ge1$ black squares, subtracting $d$ from every inner stretch shows that for $k\ge1$ exactly $\binom{n-km-d(k-1)+2k}{2k}$ rows have $k$ blocks when $n\ge km+d(k-1)$, and none otherwise.

6. A generating function

Append one extra black square at the right end. Then every red block is followed by a black square, and the longer row of $n+1$ squares splits into tiles of two kinds: a single black square, of length $1$, or a red block of $b\ge m$ squares together with the black square after it, of length $b+1\ge m+1$. Conversely, a sequence of such tiles always ends with a black square, and removing it gives a filling of $n$ squares. So $F(m,n)$ is the number of ways to write $n+1$ as an ordered sum of parts from $\{1,m+1,m+2,\dots\}$.

A generating function stores a sequence as the coefficients of a power series; multiplying two such series combines their terms in all possible ways and adds the exponents. ^[5] Let the exponent of $x$ record length. One tile has the series $t(x)=x+x^{m+1}+x^{m+2}+\dots$, which is $x+x^{m+1}/(1-x)$ by the geometric series $1/(1-x)=1+x+x^2+\dots$. Sequences of $j$ tiles have the series $t(x)^j$, and all sequences together have $1+t+t^2+\dots=1/(1-t)$. We remove the empty sequence, which is no filling, and divide by $x$ to turn the length $n+1$ back into $n$:

$$\begin{aligned}\sum_{n\ge0}F(m,n)\,x^n&=\frac1x\Bigl(\frac{1}{1-t(x)}-1\Bigr)\\&=\frac{1-x+x^m}{(1-x)^2-x^{m+1}}.\end{aligned}$$

Multiplying by the denominator $1-2x+x^2-x^{m+1}$ and comparing the coefficients of $x^n$ for $n\ge m+1$, where the numerator has none, gives $F(m,n)-2F(m,n-1)$${}+F(m,n-2)$${}-F(m,n-m-1)=0$, the recurrence of Section 4 once more. In general, a generating function is a fraction of two polynomials exactly when its coefficients satisfy, from some index on, a linear recurrence with constant coefficients, read off from the denominator. ^[5]

7. The golden ratio for $m=3$

For $m=3$ the denominator factors as $(1-x)^2-x^4$${}=(1-x-x^2)(1-x+x^2)$. The first factor belongs to the Fibonacci numbers $f_0=0$, $f_1=1$, $f_k=f_{k-1}+f_{k-2}$, whose generating function is $x/(1-x-x^2)$, ^[6] and the second one to a sequence of period $6$. This leads to an exact formula:

$$F(3,n)=\frac{f_{n+2}+p(n)}{2},$$

where $p(n)$ is $1,0,-1,-1,0,1$ when $n$ leaves the remainder $0,1,2,3,4,5$ after division by $6$. To prove it, note that for $m=3$ the recurrence of Section 4 reads $F(n)=2F(n-1)$${}-F(n-2)+F(n-4)$. The Fibonacci numbers satisfy it: using their rule three times, $f_k-2f_{k-1}+f_{k-2}$${}=-f_{k-1}+2f_{k-2}$${}=f_{k-2}-f_{k-3}=f_{k-4}$. The sequence $p$ obeys $p(n)=p(n-1)-p(n-2)$, and three uses of this rule give $p(n)-2p(n-1)+p(n-2)$${}=p(n-4)$. So their half-sum satisfies the recurrence as well, and for $n=0,1,2,3$ it takes the values $1,1,1,2$, like $F(3,n)$. The recurrence determines every later value from the four before it, so the two sequences agree everywhere.

The statement's values follow: $f_{31}=1346269$ and $p(29)=1$ give $F(3,29)=673135$, and $f_{32}=2178309$ and $p(30)=1$ give $F(3,30)=1089155$. By Binet's formula, $f_k$ is the whole number nearest to $\varphi^k/\sqrt5$, where $\varphi=(1+\sqrt5)/2\approx1.618$ is the golden ratio, ^[6] so $F(3,n)\approx\varphi^{n+2}/(2\sqrt5)$: every extra square multiplies the count by about $1.618$, and indeed $F(3,30)/F(3,29)\approx1.61803$. The On-Line Encyclopedia of Integer Sequences lists $F(3,n)$, shifted by one place, as A005252, where they count bit strings whose 1's come in groups of three or more and obey the same recurrence. ^[7]

8. How fast the counts grow

The characteristic polynomial of a linear recurrence gives its basic solutions: each root $r$ gives the solution $r^n$, and every solution is a combination of these powers, multiplied by powers of $n$ when a root is repeated. ^[8] For the recurrence of Section 4 the polynomial is

$$x^{m+1}-2x^m+x^{m-1}-1=x^{m-1}(x-1)^2-1.$$

For $x\gt1$ the product $h(x)=x^{m-1}(x-1)^2$ grows from $0$ to infinity, so exactly one real root $r_m$ is larger than $1$. It is the largest root in absolute value: if $|z|\gt1$ and $h(z)=1$, then $|z-1|\ge|z|-1$ gives $h(|z|)\le1=h(r_m)$, so $|z|\le r_m$, with equality only for $z=r_m$. Hence $F(m,n)\approx c_m\,r_m^n$ for long rows, in the sense that the ratio of the two sides tends to $1$, provided that the constant $c_m$ is not zero. The values are $r_1=2$, $r_2\approx1.7549$, $r_3=\varphi\approx1.6180$, $r_4\approx1.5289$, $r_5\approx1.4656$, $r_{10}\approx1.3034$ and $r_{50}\approx1.0990$: the longer the blocks have to be, the slower the count grows.

The constant is not zero. Write the generating function of Section 6 as $P(x)/Q(x)$, with $P(x)=1-x+x^m$ and $Q(x)=(1-x)^2-x^{m+1}$, and put $\rho=1/r_m$, so that $Q(\rho)=0$. Since $0\lt\rho\lt1$, the numerator $P(\rho)$ is positive and $Q'(\rho)=-2(1-\rho)-(m+1)\rho^m$ is negative. So $\rho$ is a simple zero of $Q$, and its term in the partial-fraction decomposition is $P(\rho)/(Q'(\rho)(x-\rho))$. ^[9] This term equals $c_m/(1-r_mx)$, whose coefficients are $c_m\,r_m^n$, with

$$\begin{aligned}c_m&=-\frac{P(\rho)}{\rho\,Q'(\rho)}\\&=\frac{r_m^2}{(m+1)r_m-(m-1)}\gt0;\end{aligned}$$

the second form uses $(1-\rho)^2=\rho^{m+1}$, which is $h(r_m)=1$ written for $\rho$. For example $c_{10}\approx0.3183$ and $c_{50}\approx0.1713$, and $c_3=\varphi^2/(2\sqrt5)$ as in Section 7. How soon this estimate becomes accurate depends on the second largest root. For $m=10$ its absolute value is about $1.1854$, and $c_{10}\,r_{10}^n$ is within $1\%$ of $F(10,56)$ and $F(10,57)$. For $m=50$ it is about $1.0870$, close to $r_{50}$, and the estimate is more than twice the true count at $n=108$ but $26\%$ too small at $n=140$, so it cannot tell where the count passes a million.

9. Scanning the lengths

The rows of $n$ squares that begin with a black square correspond to the rows of $n-1$ squares. For $n\ge m$ the row that is one red block is not among them, so $F(m,n)\ge F(m,n-1)+1$, and $F(m,n)\ge n-m+2$. The counts never decrease and grow without bound, so the least $n$ with $F(m,n)\gt10^6$ exists, and scanning $n=0,1,2,\dots$ stops exactly at the length $N$ with $F(m,N-1)\le10^6\lt F(m,N)$. For $m=1,2,\dots,10$ the scan stops at

$20, 26, 30, 35, 39,$
$43, 46, 50, 54, 57,$

in agreement with the statement for $m=3$ and $m=10$.

10. Pitfalls

The black row counts. Without it every count drops by one, for example to $16$ for the seven squares of Problem 114.
A block at the right end needs no black square after it. Demanding one after every block, as the tiling of Section 6 does without the extra square, counts exactly $F(m,n-1)$ rows and moves every threshold up by one, to $31$ for $m=3$.
"Exceeds" is strict: with $m=3$ and the target $17$, the length $7$, whose count is exactly $17$, does not qualify, and the answer would be $8$.

How the Code Works

The C++ program ^[10] keeps the minimum block length $50$, the target $10^6$ and a checkpoint flag in an Options record. parse_arguments accepts --skip-checkpoints and the numbers after --min-block= and --target=, read digit by digit by parse_int_after_prefix and parse_i64_after_prefix; any other argument, a minimum below $2$ or a target below $1$ ends the program with exit code $1$.

count_ways(length, min_block) is the recurrence of Section 3. It fills a vector dp of 64-bit integers with dp[0] = 1. For each $n$ from $1$ to length it starts from dp[n - 1], the rows that begin with a black square, and runs block from the minimum to $n$: a shorter block adds dp[n - block - 1], the fillings of what follows the block and its black square, and the block that fills the row adds $1$, a separate case because no black square follows it. solve(min_block, target) tries $n=0,1,2,\dots$ and returns the first $n$ for which count_ways exceeds the target, the scan of Section 9; it builds a fresh table for every $n$, so the counts of short rows are computed again and again. run_checkpoints checks that solve(3, 1000000) returns the statement's $30$, though not the four counts, and otherwise stops the program with exit code $2$; then main prints solve for the chosen settings.

The Python and Java programs contain the same loops, in count_ways and countWays, and the same scan, with the minimum $50$ and the target $10^6$ written into the code; they have no options and no checkpoint. Without the full-block case the loop would read the index $-1$: outside the vector in C++, an exception in Java, and in Python, where $-1$ indexes the last entry, silently wrong counts, such as $8$ instead of $7$ rows of five squares for $m=3$. Python integers have no size limit, Java uses long and C++ std::int64_t, far more than needed: for $m\ge2$ and $n\ge m+2$, Section 9 gives $F(n-m-1)\lt F(n-2)$, so the recurrence of Section 4 gives $F(n)\lt2F(n-1)$. A scan with the target $10^6$ passes $n=m+1$, where the count is $4$, so the count at which it stops is below $2\cdot10^6$, and with the default settings no count is larger. Near the 64-bit limit, however, the first count above a C++ target may not fit: with --min-block=2 --target=9000000000000000000 the count overflows, which is undefined behaviour in C++, and in our tests GCC and Clang builds print $313$ instead of the correct $79$. The two digit parsers have no overflow check either, so oversized numbers in the options are undefined behaviour too.

Complexity and Verification

Let $N$ be the length at which a scan stops. A call count_ways(L, m) runs its inner loop $\binom{L-m+2}{2}$ times for $L\ge m-1$, and the scan calls it for $L=0,1,\dots,N$, so one scan performs

$$\sum_{L=m-1}^{N}\binom{L-m+2}{2}=\binom{N-m+3}{3}$$

inner steps, which grow like the cube of $N-m$, and $N(N+1)/2$ steps of the outer loop, with memory for one table of $N+1$ numbers. The C++ checkpoint is one extra scan, with $m=3$ and $N=30$: $\binom{30}{3}=4060$ inner steps in $31$ calls. For $m=10$, $N=57$ a scan takes $\binom{50}{3}=19600$ inner steps and for $m=50$ fewer than half a million; on a current computer each program finishes within a few hundredths of a second. A single table extended until it passes the target would need only $\binom{N-m+2}{2}$ inner steps, $406$ for $m=3$, and the recurrence of Section 4 needs $O(N)$ operations.

Unless --skip-checkpoints is given, the C++ program checks the statement's $n=30$ for $m=3$ before every run. Its options also give $57$ for $m=10$, and the targets $673134$ and $673135$ with $m=3$ give $29$ and $30$, which confirms the strict comparison. Under the address and undefined-behaviour sanitizers its default run is clean, while a twenty-digit target and the 64-bit example above are reported as signed overflows. Separate programs with exact integers confirm the mathematics: a brute force over all $2^n$ colourings for $m=1,\dots,6$ and $n\le20$ agrees with the recurrences of Sections 3 and 4, the binomial sum and the generating function; these agree with one another for all $m\le60$ and $n\le400$, the Fibonacci formula holds for all $n\le150$, and these four methods reproduce the four values of the statement, the Fibonacci formula the two for $m=3$. The three published programs print the same length.

Footnotes and References

The references below supply the background facts; the recurrences, the binomial sum, the generating function, the Fibonacci formula and the operation counts are derived in the article itself.

Project Euler 115 — Counting Block Combinations II. The official statement: red blocks of at least m units, possibly of different lengths, are placed on a row of n units, separated by at least one black square, and F(m, n) counts the fillings. It gives F(3, 29) = 673135, F(3, 30) = 1089155, F(10, 56) = 880711 and F(10, 57) = 1148904 and asks for the least n for which F(50, n) first exceeds one million.
Project Euler 114 — Counting Block Combinations I. The easier version, with red blocks of at least three units and grey separating squares: a row of seven units can be filled in exactly seventeen ways, and the task is a row of fifty units.
Wikipedia — Dynamic programming. Dynamic programming, developed by Richard Bellman in the 1950s, breaks a problem into simpler subproblems recursively and stores their solutions so that each is computed only once.
Wikipedia — Stars and bars (combinatorics). The number of k-tuples of nonnegative integers with sum n is C(n + k − 1, k − 1): n stars are split into k groups by k − 1 bars.
Wikipedia — Generating function. A generating function holds a sequence as the coefficients of a formal power series; multiplication gives the convolution of sequences, 1, 1, 1, … has the generating function 1/(1 − x), and an ordinary generating function is rational exactly when its sequence satisfies a linear recurrence with constant coefficients, whose coefficients are those of the denominator.
Wikipedia — Fibonacci sequence. The Fibonacci numbers satisfy F₀ = 0, F₁ = 1 and Fₙ = Fₙ₋₁ + Fₙ₋₂; their generating function is z/(1 − z − z²), and by Binet's formula Fₙ is the integer closest to φⁿ/√5, where φ is the golden ratio.
OEIS A005252. The sequence 1, 1, 1, 1, 2, 4, 7, 11, 17, 27, …, a(n) = Σ binomial(n − 2k, 2k); a(n+1) is the number of n-bit sequences in which the 1's appear in groups of three or more, a(n) = 2a(n−1) − a(n−2) + a(n−4), and a formula combines Fibonacci numbers with a term of period 6.
Wikipedia — Linear recurrence with constant coefficients. The coefficients give the characteristic polynomial; with distinct roots every solution is a combination of powers of the roots fixed by the initial values, and a repeated root adds such powers times powers of the index.
Wikipedia — Partial fraction decomposition. A fraction P(x)/Q(x) of polynomials is written as a polynomial, which is zero when P has the lower degree, plus fractions with simpler denominators; by the residue method, a simple root a of Q contributes the term P(a)/Q′(a) · 1/(x − a), which Section 8 uses at the root 1/rₘ.
C++ — Euler115.cpp. The linked immutable C++ revision contains parse_arguments, count_ways, solve, run_checkpoints and the options --min-block, --target and --skip-checkpoints. It is the implementation record for this article.

Problem 115 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    int min_block = 50;
    i64 target = 1000000;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_i64_after_prefix(arg, "--target=", options.target)) {
            continue;
        }

        if (parse_int_after_prefix(arg, "--min-block=", options.min_block)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.min_block >= 2 && options.target >= 1;
}

i64 count_ways(const int length, const int min_block) {
    std::vector<i64> dp(static_cast<std::size_t>(length + 1), 0);
    dp[0] = 1;

    for (int n = 1; n <= length; ++n) {
        i64 ways = dp[static_cast<std::size_t>(n - 1)];

        for (int block = min_block; block <= n; ++block) {
            if (block == n) {
                ways += 1;
            } else {
                ways += dp[static_cast<std::size_t>(n - block - 1)];
            }
        }

        dp[static_cast<std::size_t>(n)] = ways;
    }

    return dp[static_cast<std::size_t>(length)];
}

int solve(const int min_block, const i64 target) {
    for (int n = 0;; ++n) {
        if (count_ways(n, min_block) > target) {
            return n;
        }
    }
}

bool run_checkpoints() {
    if (solve(3, 1000000) != 30) {
        std::cerr << "Checkpoint failed for min_block=3" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.min_block, options.target) << '\n';
    return 0;
}

Python

# Problem 115: Counting block combinations II
# Find minimum n where count_ways(n, 50) exceeds 1 million.

def count_ways(length, min_block):
    dp = [0] * (length + 1)
    dp[0] = 1
    for n in range(1, length + 1):
        dp[n] = dp[n - 1]
        for block in range(min_block, n + 1):
            dp[n] += 1 if block == n else dp[n - block - 1]
    return dp[length]

def solve():
    n = 0
    while True:
        if count_ways(n, 50) > 1000000:
            print(n)
            return
        n += 1

solve()

Java

public class Euler115 {
    static long countWays(int len, int minBlock) {
        long[] dp=new long[len+1]; dp[0]=1;
        for(int n=1;n<=len;n++){dp[n]=dp[n-1];for(int b=minBlock;b<=n;b++)dp[n]+=(b==n)?1:dp[n-b-1];}
        return dp[len];
    }
    public static void main(String[] args) {
        for(int n=0;;n++)if(countWays(n,50)>1000000){System.out.println(n);return;}
    }
}