Problem 150: Searching a Triangular Array for a Sub-Triangle Having the Minimum-Sum

Project Euler Problem 150 Solution

EulerSolve provides an optimized solution for Project Euler Problem 150, Searching a Triangular Array for a Sub-Triangle Having the Minimum-Sum, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The problem constructs a downward triangular array with $n=1000$ rows, so the total number of entries is $1+2+\cdots+1000=500{,}500$. The entries are generated in row-major order by the linear congruential recurrence $t_0=0$, $t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}$, and $s_k=t_k-2^{19}$. We must find the downward-pointing sub-triangle whose total sum is as small as possible. If every candidate sub-triangle were summed from scratch, the computation would be far too slow. The key mathematical observation is that increasing the height of a sub-triangle adds exactly one contiguous segment on the next row, so row prefix sums turn each extension into an $O(1)$ update. Mathematical Approach Let the generated triangle be $a_{r,c}$ with $0\le c\le r<n$. A sub-triangle is determined by its apex $(r,c)$ and its height $h\ge 1$. Its sum is $$T(r,c,h)=\sum_{i=0}^{h-1}\sum_{j=0}^{i} a_{r+i,c+j},\qquad 1\le h\le n-r.$$ The problem is to minimize $T(r,c,h)$ over all valid triples $(r,c,h)$. Encoding the triangular array The pseudo-random generator is part of the mathematics, not just an implementation detail, because the data set is defined by that recurrence alone. After generating $s_1,s_2,\dots$, the values are placed row by row: one value in the first row, two in the second, three in the third, and so on until row 1000 is complete....

Detailed mathematical approach

Problem Summary

A triangular array of positive and negative integers has $1000$ rows: the first row holds one number, the second two numbers, and so on, $1+2+\dots+1000=500500$ numbers in all. They come from a linear congruential generator: starting from $t=0$, for $k=1,2,\dots,500500$ we set

$$\begin{aligned}t&:=(615949\,t+797807)\bmod 2^{20},\\s_k&:=t-2^{19},\end{aligned}$$

so every $s_k$ lies between $-2^{19}$ and $2^{19}-1$. The statement gives $s_1=273519$, $s_2=-153582$ and $s_3=450905$. The numbers fill the rows in order: $s_1$ forms the first row, $s_2,s_3$ the second, $s_4,s_5,s_6$ the third, and so on. A sub-triangle starts at any entry and extends down as far as we like, taking in the two entries directly below it in the next row, the three entries directly below those in the row after that, and so on; its sum is the sum of all the entries it contains. We must find the smallest possible sub-triangle sum. In a small example array of six rows, the statement marks a sub-triangle with sum $-42$, the smallest there. ^[1]

The whole solution in one sentence: fix the top entry of a sub-triangle and let the triangle grow one row at a time; each new row adds a run of neighbouring entries whose sum is the difference of two running totals of that row, so each of the $167\,167\,000$ sub-triangle sums costs one subtraction and one addition, and we keep the smallest.

Mathematical Approach

After fixing coordinates and counting the sub-triangles, we obtain every sum in a single step from running totals along the rows.

1. The array and its generator

Rows and columns are counted from $0$, so the first row is row $0$: row $r=0,1,\dots,n-1$, with $n=1000$, holds the entries $a_{r,0},\dots,a_{r,r}$ from left to right. Rows $0$ to $r-1$ hold $1+2+\dots+r=r(r+1)/2$ numbers, so

$$a_{r,c}=s_k,\quad k=\frac{r(r+1)}{2}+c+1.$$

For example $a_{0,0}=s_1$, $a_{1,1}=s_3$, and the last entry $a_{999,999}$ is $s_{500500}$. The first value of $t$ is $797807$, so $s_1=797807-524288=273519$; the next values $370706$, $975193$, $529396$, $813011$, $427046$ give $s_2$, $s_3$ and row $2$: $5108$, $288723$, $-97242$.

By the Hull–Dobell theorem, a generator that multiplies by a constant, adds a constant and reduces modulo $2^{20}$ runs through all $2^{20}$ residues before repeating exactly when the added constant is odd and the multiplier minus $1$ is divisible by $4$. ^[2] Both hold: $797807$ is odd and $615948=4\cdot153987$. Since $500500\lt2^{20}=1048576$, the $500500$ values of $t$ are all different, and so are the entries of the array.

2. Sub-triangles

The sub-triangle $\Delta(r,c,h)$ has its apex at $a_{r,c}$ and height $h$: from row $r+i$, for $i=0,1,\dots,h-1$, it takes the $i+1$ entries in columns $c$ to $c+i$. The two entries directly below $a_{r,c}$ are $a_{r+1,c}$ and $a_{r+1,c+1}$, and the triangle may stop at any row, even at its first one, so a single entry is a sub-triangle too and $1\le h\le n-r$. Its sum is

$$T(r,c,h)=\sum_{i=0}^{h-1}\ \sum_{j=0}^{i}a_{r+i,\,c+j}.$$

The example array of the statement has the six rows

$$\begin{array}{c}15\\{-14}\quad{-7}\\20\quad{-13}\quad{-5}\\{-3}\quad8\quad23\quad{-26}\\1\quad{-4}\quad{-5}\quad{-18}\quad5\\{-16}\quad31\quad2\quad9\quad28\quad3\end{array}$$

and its marked sub-triangle is $\Delta(1,1,4)$, with the rows $-7$; $-13,-5$; $8,23,-26$; $-4,-5,-18,5$, whose sums $-7$, $-18$, $5$ and $-22$ add up to $-42$.

3. How many sub-triangles there are

A sub-triangle is fixed by its apex and its bottom row $b=r+h-1$. For a given bottom row $b$, the apex may be any entry of rows $0$ to $b$, which gives $1+2+\dots+(b+1)$${}=(b+1)(b+2)/2$ choices, a triangular number. Adding them up over all bottom rows gives a tetrahedral number: ^[3]

$$\sum_{b=0}^{n-1}\frac{(b+1)(b+2)}{2}=\binom{n+2}{3},$$

where the binomial coefficient is $\binom{n+2}{3}=n(n+1)(n+2)/6$. Induction on $n$ proves this: for $n=1$ both sides equal $1$, and from $n-1$ to $n$ the right-hand side grows by $n(n+1)/6$ times $(n+2)-(n-1)=3$, that is, by $n(n+1)/2$, the new term for $b=n-1$. The six-row example has $56$ sub-triangles, and the real array has $167\,167\,000$.

4. Summing from scratch is too slow

A sub-triangle of height $h$ has its apex in one of the rows $0$ to $n-h$, so there are $N_h=(n-h+1)(n-h+2)/2$ of them, and each contains $1+2+\dots+h=h(h+1)/2$ entries. Adding up every sub-triangle separately therefore handles

$$W(n)=\sum_{h=1}^{n}N_h\,\frac{h(h+1)}{2}$$

entries. For the six-row example the heights $1$ to $6$ contribute $21,45,60,60,45,21$, in total $252$. For $n=1000$ we get $W(n)=8\,416\,958\,750\,200$${}\approx8.4\cdot10^{12}$, so an average sub-triangle has about $50\,350$ entries. Even at $10^9$ additions per second this would take more than two hours. The cure is to reuse work: a sub-triangle of height $h+1$ is a sub-triangle of height $h$ plus one more row.

5. Running totals along a row

For each row $r$ we store its running totals, or prefix sums, ^[4]

$$\begin{aligned}P_r(0)&=0,\\P_r(j)&=a_{r,0}+a_{r,1}+\dots+a_{r,j-1},\end{aligned}$$

for $1\le j\le r+1$. The run of $\ell$ consecutive entries of row $r$ that starts in column $c$ then has the sum

$$R_r(c,\ell)=P_r(c+\ell)-P_r(c),$$

because the first $c$ terms of $P_r(c+\ell)$ add up to $P_r(c)$ and cancel. For row $4$ of the example, $1,-4,-5,-18,5$, the running totals are $0,1,-3,-8,-26,-21$, and the four entries from column $1$ on sum to $R_4(1,4)=P_4(5)-P_4(1)$${}=-21-1=-22$. In row $r+i$ the sub-triangle $\Delta(r,c,h)$ takes the run of $i+1$ entries from column $c$, so

$$T(r,c,h)=\sum_{i=0}^{h-1}R_{r+i}(c,\,i+1).$$

This replaces the $h(h+1)/2$ entries of a sub-triangle by $h$ differences, in total $\sum_h hN_h=41\,917\,125\,250$${}\approx4.2\cdot10^{10}$ for $n=1000$. The next step removes the remaining factor $h$.

6. Growing a sub-triangle by one row

$\Delta(r,c,h+1)$ consists of $\Delta(r,c,h)$ and, below it, the run of $h+1$ entries of row $r+h$ from column $c$ to column $c+h$; the two parts do not overlap. Hence, with $T(r,c,0)=0$ for the empty triangle,

$$\begin{aligned}T(r,c,h+1)&=T(r,c,h)\\&\quad+R_{r+h}(c,\,h+1).\end{aligned}$$

Once the running totals are stored, every sub-triangle sum costs one subtraction and one addition, given the sum of the sub-triangle with the same apex and one row less. All $\binom{n+2}{3}$ sums of Section 3 are thus formed in $\binom{n+2}{3}$ steps, and the smallest of them is the answer.

7. The example worked out

For the apex $a_{1,1}=-7$ of the example, the runs added for the heights $1$ to $5$ are $-7$, $-13-5=-18$, $8+23-26=5$, $-4-5-18+5=-22$ and $31+2+9+28+3=73$, so the sums are

$$-7,\quad-25,\quad-20,\quad-42,\quad31.$$

The fourth is the $-42$ of the statement. The list also shows a pitfall: the sum goes up from $-25$ to $-20$ before it falls to $-42$, so a program that stopped growing a sub-triangle as soon as its sum increased would miss the minimum. Computing all $56$ sums confirms that $-42$ is the smallest and that only $\Delta(1,1,4)$ reaches it; the next best is $\Delta(3,3,2)$, with $-26-18+5=-39$. The minimum is neither the smallest entry, $-26$, nor the whole array, whose sum is $34$.

8. One top row at a time

The rule of Section 6 can be run in two orders. The Java program fixes an apex and lets the height grow. The C++ and Python programs fix the top row $r$ and keep one total $A_c$ for each apex column $c=0,\dots,r$, all starting at $0$; then they move the bottom row $b$ from $r$ down to $n-1$ and add to every $A_c$ the run sum $R_b(c,\,b-r+1)$, which covers columns $c$ to $c+b-r$ of row $b$. By induction on $b$, after row $b$ has been processed $A_c=T(r,c,b-r+1)$: this holds before the first step, when every $A_c$ is the empty sum $0$, and each step is exactly the rule of Section 6 with $h=b-r$. For the top row $r=1$ of the example, the pair $(A_0,A_1)$ becomes $(-14,-7)$, $(-7,-25)$, $(21,-20)$, $(-5,-42)$ and $(49,31)$ as $b$ runs from $1$ to $5$. Either order visits every triple $(r,c,h)$ exactly once, so the smallest value seen is the smallest sub-triangle sum.

9. How large the numbers get

Every entry has absolute value at most $2^{19}=524288$. A running total adds at most $1000$ entries, so $|P_r(j)|\le524\,288\,000$, which fits into a signed 32-bit integer, whose largest value is $2^{31}-1=2\,147\,483\,647$. A sub-triangle, however, may contain up to $500\,500$ entries, and the resulting bound $500\,500\cdot2^{19}\approx2.6\cdot10^{11}$ for its sum is far beyond $2^{31}-1$, though far below the 64-bit limit $2^{63}-1\approx9.2\cdot10^{18}$. This bound guarantees that every sum fits into the 64-bit integers used by C++ and Java, and Python's integers are unbounded. ^[7] The generator needs 64 bits too: before the reduction modulo $2^{20}$, $615949\,t+797807$ can be as large as about $6.5\cdot10^{11}$.

10. Checkpoints for fewer rows

Let $F(n)$ be the smallest sub-triangle sum of the array formed by the first $n$ rows of the generated numbers. A sub-triangle of the first $n$ rows is also one of the first $n+1$ rows, so $F(n+1)\le F(n)$. A brute force gives $F(1)=273519$, $F(2)=F(3)=s_2$, $F(4)=\dots=F(7)=-488152$, the single entry $s_8=a_{3,1}$, then $F(10)=-1495491$, reached by $\Delta(6,3,4)$, and $F(30)=-6318831$, reached by $\Delta(7,6,22)$. The last value is already far below $-2^{19}$, the smallest possible entry, so for the full array the minimum is certainly not a single entry.

11. Other ways to the same sums

The sums can also be built without running totals. The two sub-triangles of height $h-1$ with apexes $a_{r+1,c}$ and $a_{r+1,c+1}$ together cover all of $\Delta(r,c,h)$ except its apex, and they overlap exactly in $\Delta(r+2,c+1,h-2)$. By the inclusion–exclusion principle, ^[5] for $h\ge2$

$$\begin{aligned}&T(r,c,h)\\&\quad=a_{r,c}+T(r+1,c,h-1)\\&\qquad+T(r+1,c+1,h-1)\\&\qquad-T(r+2,c+1,h-2),\end{aligned}$$

where a sum of height $0$ is $0$. This also costs a few additions per sub-triangle, but it keeps the sums of all sub-triangles of the two previous heights, about $n^2$ numbers, instead of one total per apex column; it serves as an independent check below.

How the Code Works

The C++ program ^[6] starts in main with the defaults of Options: $1000$ rows and the checkpoint switched on. parse_arguments accepts --skip-checkpoints and --rows= followed by digits, which parse_int_after_prefix reads; an unknown argument or a row count below $1$ ends the program with exit code $1$. parse_int_after_prefix does not check the size of the number, so for instance --rows=4294967297 overflows int, which is undefined behaviour; the default run reads no number. run_checkpoints builds the six-row example of Section 2 and requires min_subtriangle_sum to return $-42$, otherwise the exit code is $2$. Then main prints solve(rows), which passes the array made by generate_triangle to min_subtriangle_sum.

generate_triangle runs the generator of Section 1 in a 64-bit variable t, as (615949LL * t + 797807LL) % (1LL << 20), and stores $t-2^{19}$ row by row as int in a std::vector<std::vector<int>>. min_subtriangle_sum first builds the running totals of Section 5: prefix[r] has $r+2$ entries of type i64, an alias of std::int64_t, with prefix[r][0] equal to $0$. It sets best to the largest i64 and runs the loops of Section 8: for every top a vector accum of top + 1 zeros, for every bottom from top on the value height = bottom - top, which is the $h$ of Section 6, one less than the number of rows after the update, and for every column c up to top the run sum prefix[bottom][c + height + 1] - prefix[bottom][c] of Section 5, which is added to accum[c]; then best becomes the smaller of itself and accum[c].

The Python program repeats the generation, the running totals and these loops inside one function solve, with the row count fixed at $1000$ and no options or checkpoint. Its integers have unlimited precision; best starts at float('inf') and becomes an integer at the first comparison, and the result is returned as a string. The Java program computes each entry and its running total in the same loop and writes the generator as (615949 * t + 797807) & ((1L << 20) - 1): since $2^{20}-1$ is twenty binary ones, the bitwise AND keeps the last twenty binary digits of the nonnegative number, which is its remainder modulo $2^{20}$. It stores the entries in int[][] and the running totals in long[][] and uses the other order of Section 8: for every apex (r, c), a sum s grows while r + h < rows, and after the update for a given h it equals $T(r,c,h+1)$.

Complexity and Verification

Generating the array and building its running totals take $500\,500$ steps each, a number of order $n^2$. The main loops perform one update and one comparison for each of the $\binom{n+2}{3}=167\,167\,000$ sub-triangles, so the running time grows like $n^3/6$, with a very small cost per step. The memory is dominated by the array and the running totals, $500\,500$ and $501\,500$ numbers, in C++ and Java about $2$ MB of 32-bit entries and $4$ MB of 64-bit totals, while accum in C++ and Python holds at most $1000$ values. Python's lists hold references to separate integer objects, about $40$ MB for the same data, and its interpreted loops are much slower. In tests on a desktop computer (GCC with -O2, Java 17, CPython 3.11), the C++ and Java programs finished in well under a second and the Python program in about ten seconds.

Before the main computation the C++ program checks the example of the statement, $-42$; the Python and Java programs contain no checks. For this article all three programs were run and print the same number. A brute force that adds up every sub-triangle from scratch agrees with the C++ program, run with --rows=$n$, for every $n\le60$, and a separate implementation of the method of Section 8 agrees with it for every $n\le150$. An independent program that uses the inclusion–exclusion rule of Section 11, without running totals, forms exactly $167\,167\,000$ sums for the full array and finds the same minimum as the three published programs. The counts of Sections 3 and 4 were confirmed by enumeration for every $n\le12$, and the numbers of Sections 1, 7 and 10 were recomputed in the same way. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The coordinates of the sub-triangles, the counts, the one-step rule and the checks are derived explicitly in this article.

Project Euler 150 — Sub-triangle Sums. The official statement fills a triangular array of 1000 rows with the 500500 numbers sₖ = t − 2¹⁹, where t := (615949·t + 797807) mod 2²⁰ starting from t = 0, gives s₁, s₂, s₃ and a small example whose smallest sub-triangle sum is −42, lets a sub-triangle start at any element and extend down as far as we like, and asks for the smallest possible sub-triangle sum.
Wikipedia — Linear congruential generator. For a nonzero increment c, the Hull–Dobell theorem states that the generator has the full period m for every seed if and only if m and c are coprime, a − 1 is divisible by all prime factors of m, and a − 1 is divisible by 4 if m is divisible by 4. For m = 2²⁰ the only prime factor is 2.
Wikipedia — Tetrahedral number. The n-th tetrahedral number is the sum of the first n triangular numbers and equals the binomial coefficient C(n + 2, 3) = n(n + 1)(n + 2)/6.
Wikipedia — Prefix sum. The prefix sums, or cumulative sums, of a sequence are its running totals, y₀ = x₀, y₁ = x₀ + x₁, and so on. An exclusive scan leaves out the current term, and the example in the article starts it with 0, like the totals Pᵣ(j) of Section 5.
Wikipedia — Inclusion–exclusion principle. For two finite sets, |A ∪ B| = |A| + |B| − |A ∩ B|: the elements of the overlap are counted twice and then subtracted once. Section 11 applies the same correction to sums of entries.
C++ — Euler150.cpp. The linked immutable C++ revision contains parse_arguments, generate_triangle, min_subtriangle_sum, solve and run_checkpoints with the six-row example. It is the implementation record for this article.
cppreference — Fixed width integer types: std::int64_t is a signed integer type with a width of exactly 64 bits. Java Language Specification, §4.2.1: int has the range −2³¹ to 2³¹ − 1 and long the range −2⁶³ to 2⁶³ − 1. Python — numeric types: integers have unlimited precision.

Problem 150 source code

C++

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

namespace {

using i64 = std::int64_t;

struct Options {
    int rows = 1000;
    bool run_checkpoints = 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_int_after_prefix(arg, "--rows=", options.rows)) {
            continue;
        }

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

    return options.rows >= 1;
}

std::vector<std::vector<int>> generate_triangle(const int rows) {
    std::vector<std::vector<int>> triangle(static_cast<std::size_t>(rows));

    std::int64_t t = 0;
    for (int r = 0; r < rows; ++r) {
        triangle[static_cast<std::size_t>(r)].reserve(static_cast<std::size_t>(r + 1));
        for (int c = 0; c <= r; ++c) {
            t = (615949LL * t + 797807LL) % (1LL << 20);
            triangle[static_cast<std::size_t>(r)].push_back(static_cast<int>(t - (1LL << 19)));
        }
    }

    return triangle;
}

i64 min_subtriangle_sum(const std::vector<std::vector<int>>& triangle) {
    const int rows = static_cast<int>(triangle.size());

    std::vector<std::vector<i64>> prefix(static_cast<std::size_t>(rows));
    for (int r = 0; r < rows; ++r) {
        prefix[static_cast<std::size_t>(r)].resize(static_cast<std::size_t>(r + 2), 0);
        for (int c = 0; c <= r; ++c) {
            prefix[static_cast<std::size_t>(r)][static_cast<std::size_t>(c + 1)] =
                prefix[static_cast<std::size_t>(r)][static_cast<std::size_t>(c)] +
                triangle[static_cast<std::size_t>(r)][static_cast<std::size_t>(c)];
        }
    }

    i64 best = std::numeric_limits<i64>::max();

    for (int top = 0; top < rows; ++top) {
        std::vector<i64> accum(static_cast<std::size_t>(top + 1), 0);

        for (int bottom = top; bottom < rows; ++bottom) {
            const int height = bottom - top;

            for (int c = 0; c <= top; ++c) {
                const i64 row_segment =
                    prefix[static_cast<std::size_t>(bottom)][static_cast<std::size_t>(c + height + 1)] -
                    prefix[static_cast<std::size_t>(bottom)][static_cast<std::size_t>(c)];
                accum[static_cast<std::size_t>(c)] += row_segment;
                best = std::min(best, accum[static_cast<std::size_t>(c)]);
            }
        }
    }

    return best;
}

i64 solve(const int rows) {
    return min_subtriangle_sum(generate_triangle(rows));
}

bool run_checkpoints() {
    const std::vector<std::vector<int>> sample = {
        {15},
        {-14, -7},
        {20, -13, -5},
        {-3, 8, 23, -26},
        {1, -4, -5, -18, 5},
        {-16, 31, 2, 9, 28, 3},
    };

    if (min_subtriangle_sum(sample) != -42) {
        std::cerr << "Checkpoint failed for statement sample triangle" << '\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.rows) << '\n';
    return 0;
}

Python

def solve():
    rows = 1000
    triangle = []
    t = 0
    for r in range(rows):
        row = []
        for c in range(r + 1):
            t = (615949 * t + 797807) % (1 << 20)
            row.append(t - (1 << 19))
        triangle.append(row)

    prefix = []
    for r in range(rows):
        prow = [0] * (r + 2)
        for c in range(r + 1):
            prow[c + 1] = prow[c] + triangle[r][c]
        prefix.append(prow)

    best = float('inf')
    for top in range(rows):
        accum = [0] * (top + 1)
        for bottom in range(top, rows):
            height = bottom - top
            for c in range(top + 1):
                row_segment = prefix[bottom][c + height + 1] - prefix[bottom][c]
                accum[c] += row_segment
                if accum[c] < best:
                    best = accum[c]
    return str(best)

if __name__ == '__main__':
    print(solve())

Java

public class Euler150 {
    public static void main(String[] args) {
        int rows = 1000;
        long t = 0;
        int[][] tri = new int[rows][];
        long[][] prefix = new long[rows][];
        for (int i = 0; i < rows; i++) {
            tri[i] = new int[i + 1];
            prefix[i] = new long[i + 2];
            for (int j = 0; j <= i; j++) {
                t = (615949 * t + 797807) & ((1L << 20) - 1);
                tri[i][j] = (int) (t - (1 << 19));
                prefix[i][j + 1] = prefix[i][j] + tri[i][j];
            }
        }
        long best = Long.MAX_VALUE;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c <= r; c++) {
                long s = 0;
                for (int h = 0; r + h < rows; h++) {
                    s += prefix[r + h][c + h + 1] - prefix[r + h][c];
                    if (s < best)
                        best = s;
                }
            }
        System.out.println(best);
    }
}