Problem 432: Totient Sum

Project Euler Problem 432 Solution

EulerSolve provides an optimized solution for Project Euler Problem 432, Totient Sum, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We need to evaluate $$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$ for $n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17$ and $m=10^{11}$, then report the last 9 digits. A direct loop over $10^{11}$ terms is impossible, so the solution must exploit the arithmetic structure of $n$ and the summatory behavior of Euler's totient. Mathematical Approach Let $$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$ Since $n$ is squarefree, $$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$ The implementation turns the original sum into a weighted sum of values of $\Phi$. Step 1: Use That $n$ Is Squarefree Fix an integer $i$, and write its prime factorization locally as $p^a\parallel i$. The contribution of each prime to $\varphi(ni)/\varphi(n)$ depends on whether that prime already divides $n$. If $p\notin P$, then $p$ is coprime to $n$, so multiplicativity gives $$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$ If $p\in P$, then $n$ already contains one factor of $p$, and because $n$ is squarefree we get $$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$ Now use the classical identity $$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$ Therefore the local factor can be written as $$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P....

Detailed mathematical approach

Problem Summary

We need to evaluate

$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$

for $n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17$ and $m=10^{11}$, then report the last 9 digits. A direct loop over $10^{11}$ terms is impossible, so the solution must exploit the arithmetic structure of $n$ and the summatory behavior of Euler's totient.

Mathematical Approach

Let

$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$

Since $n$ is squarefree,

$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$

The implementation turns the original sum into a weighted sum of values of $\Phi$.

Step 1: Use That $n$ Is Squarefree

Fix an integer $i$, and write its prime factorization locally as $p^a\parallel i$. The contribution of each prime to $\varphi(ni)/\varphi(n)$ depends on whether that prime already divides $n$.

If $p\notin P$, then $p$ is coprime to $n$, so multiplicativity gives

$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$

If $p\in P$, then $n$ already contains one factor of $p$, and because $n$ is squarefree we get

$$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$

Now use the classical identity

$$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$

Therefore the local factor can be written as

$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$

Multiplying these local identities over all prime powers dividing $i$ yields a restricted divisor sum. If we call an integer $d$ $P$-smooth when all prime divisors of $d$ lie in $P$, then

$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$$

This is the crucial transformation behind the whole solver.

Step 2: Swap the Order of Summation

Insert the identity above into $S(n,m)$:

$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).$$

Now write $i=dk$. For each fixed $P$-smooth $d\le m$, the inner variable $k$ ranges from $1$ to $\left\lfloor m/d\right\rfloor$. Hence

$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$$

With the summatory totient function $\Phi$, this becomes

$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$

So the original problem is reduced to two tasks:

1. enumerate all $P$-smooth numbers $d\le m$;

2. evaluate $\Phi(x)$ quickly for the quotients $x=\left\lfloor m/d\right\rfloor$.

Step 3: Enumerate the Relevant Smooth Numbers

Because $P$ has only seven primes, every relevant $d$ has the form

$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$

A depth-first search over the exponent choices generates every such value exactly once. This is practical because the smoothness condition is extremely restrictive compared with all integers up to $10^{11}$.

For the actual parameters, the enumeration contains only $152751$ smooth numbers. Many of them lead to the same quotient $\left\lfloor m/d\right\rfloor$, so the implementation deduplicates those quotients before evaluating $\Phi$.

Step 4: Compute the Summatory Totient Fast

The key identity is

$$\sum_{d\mid t}\varphi(d)=t.$$

Summing over $1\le t\le x$ gives

$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$$

If we write the triangular number as

$$T(x)=\frac{x(x+1)}{2},$$

then isolating the $u=1$ term yields the recursion

$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$

The floor quotient stays constant on intervals. If

$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$$

then $\left\lfloor x/u\right\rfloor=q$ for every $u\in[\ell,r]$, so the recursion can be blocked as

$$\Phi(x)=T(x)-\sum_{\text{quotient blocks}}(r-\ell+1)\,\Phi(q).$$

This reduces the work dramatically, because the number of distinct floor quotients is only $O(\sqrt{x})$. The implementation stores small values in a totient-prefix table and memoizes large recursive calls.

Worked Example

It is helpful to test the formula on a smaller squarefree value, say $n=6=2\cdot 3$ and $m=5$. Then $P=\{2,3\}$, $\varphi(6)=2$, and the $P$-smooth numbers up to $5$ are

$$1,2,3,4.$$

Therefore

$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$

Since

$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$

we get

$$S(6,5)=2(10+2+1+1)=28.$$

Direct verification matches:

$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$

How the Code Works

The C++, Python, and Java implementations use the same arithmetic strategy. First they factor $n$, compute $\varphi(n)$, and generate every $P$-smooth number $d\le m$. Next they form the quotient list $\left\lfloor m/d\right\rfloor$, sort it, remove duplicates, and evaluate each distinct $\Phi(q)$ only once.

For small $q$, the implementation uses a linear totient sieve and prefix sums up to $12000000$. For larger $q$, it applies the quotient-block recursion above and memoizes the results. After all required $\Phi(q)$ values are available, it sums them with multiplicity, multiplies by $\varphi(n)$, and obtains $S(n,m)$.

The implementation also validates itself before attacking $10^{11}$: it compares against direct summation for several small values of $m$, and it checks the published checkpoint

$$S(510510,10^6)=45480596821125120.$$

The final accumulation can be split across multiple threads, but the arithmetic formula itself is unchanged.

Complexity Analysis

Let $A(m)$ be the number of $P$-smooth integers $d\le m$, and let

$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}.$$

Enumerating the smooth numbers costs $O(A(m))$. Sorting and deduplicating the quotients costs $O(A(m)\log A(m))$. Each new summatory-totient value $\Phi(q)$ is computed by quotient blocking plus memoization, so a single uncached query touches only the distinct floor-division blocks, which is $O(\sqrt{q})$ in the classical analysis.

For the actual input,

$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$

which explains why the method is feasible even though the original sum has $10^{11}$ terms. Memory usage is dominated by the totient-prefix table, the memoization cache, and the arrays storing the smooth numbers and quotient values.

References

Problem page: https://projecteuler.net/problem=432
Euler totient function: Wikipedia — Euler's totient function
Smooth number: Wikipedia — Smooth number
Dirichlet hyperbola method: Wikipedia — Dirichlet hyperbola method
Apostol, T. M. Introduction to Analytic Number Theory, Chapters 2-3.

Problem 432 source code

C++

#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <thread>
#include <unordered_map>
#include <vector>

namespace {

using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = unsigned __int128;

constexpr u64 kN = 510'510ULL;
constexpr u64 kCheckpointM = 1'000'000ULL;
constexpr u64 kTargetM = 100'000'000'000ULL;
constexpr u64 kExpectedCheckpoint = 45'480'596'821'125'120ULL;
constexpr u64 kLastDigitsMod = 1'000'000'000ULL;
constexpr u64 kTotientSieveLimit = 12'000'000ULL;

struct U64Hash {
    std::size_t operator()(u64 value) const noexcept {
        value += 0x9e3779b97f4a7c15ULL;
        value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
        value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
        value ^= (value >> 31);
        return static_cast<std::size_t>(value);
    }
};

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }

    std::string digits;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        digits.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(digits.begin(), digits.end());
    return digits;
}

u128 triangular_u128(u64 value) {
    return static_cast<u128>(value) * (value + 1) / 2;
}

u64 euler_phi_u64(u64 value) {
    if (value == 0) {
        return 0;
    }

    u64 result = value;
    u64 n = value;

    for (u64 p = 2; p * p <= n; ++p) {
        if (n % p != 0) {
            continue;
        }
        while (n % p == 0) {
            n /= p;
        }
        result -= result / p;
    }
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

std::vector<u64> distinct_prime_factors(u64 n) {
    std::vector<u64> factors;
    for (u64 p = 2; p * p <= n; ++p) {
        if (n % p != 0) {
            continue;
        }
        factors.push_back(p);
        while (n % p == 0) {
            n /= p;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

void generate_smooth_numbers_dfs(const std::vector<u64>& primes,
                                 std::size_t index,
                                 u64 current,
                                 u64 limit,
                                 std::vector<u64>& out) {
    if (index == primes.size()) {
        out.push_back(current);
        return;
    }

    u64 value = current;
    const u64 prime = primes[index];
    while (value <= limit) {
        generate_smooth_numbers_dfs(primes, index + 1, value, limit, out);
        if (value > limit / prime) {
            break;
        }
        value *= prime;
    }
}

std::vector<u64> generate_smooth_numbers(const std::vector<u64>& primes, u64 limit) {
    std::vector<u64> smooth;
    smooth.reserve(200'000);
    generate_smooth_numbers_dfs(primes, 0, 1, limit, smooth);
    return smooth;
}

unsigned choose_thread_count(bool allow_multithreading,
                             unsigned requested_threads,
                             std::size_t workload) {
    if (!allow_multithreading || workload < 100'000) {
        return 1;
    }

    unsigned threads = requested_threads;
    if (threads == 0) {
        threads = std::thread::hardware_concurrency();
        if (threads == 0) {
            threads = 1;
        }
    }

    threads = std::max(1u, std::min<unsigned>(threads, static_cast<unsigned>(workload)));
    return threads;
}

class TotientSummatory {
public:
    explicit TotientSummatory(u64 sieve_limit)
        : sieve_limit_(sieve_limit),
          phi_(static_cast<std::size_t>(sieve_limit_) + 1, 0),
          prefix_(static_cast<std::size_t>(sieve_limit_) + 1, 0) {
        build_totients();
        large_cache_.reserve(1 << 20);
    }

    u128 sum_phi(u64 n) {
        if (n <= sieve_limit_) {
            return prefix_[static_cast<std::size_t>(n)];
        }

        const auto it = large_cache_.find(n);
        if (it != large_cache_.end()) {
            return it->second;
        }

        u128 result = triangular_u128(n);
        for (u64 left = 2, right = 0; left <= n; left = right + 1) {
            const u64 quotient = n / left;
            right = n / quotient;
            result -= static_cast<u128>(right - left + 1) * sum_phi(quotient);
        }

        large_cache_.emplace(n, result);
        return result;
    }

private:
    u64 sieve_limit_ = 0;
    std::vector<u32> phi_;
    std::vector<u64> prefix_;
    std::unordered_map<u64, u128, U64Hash> large_cache_;

    void build_totients() {
        std::vector<int> primes;
        primes.reserve(static_cast<std::size_t>(sieve_limit_ / 10));
        std::vector<char> is_composite(static_cast<std::size_t>(sieve_limit_) + 1, 0);

        if (sieve_limit_ >= 1) {
            phi_[1] = 1;
        }

        for (u64 i = 2; i <= sieve_limit_; ++i) {
            if (!is_composite[static_cast<std::size_t>(i)]) {
                primes.push_back(static_cast<int>(i));
                phi_[static_cast<std::size_t>(i)] = static_cast<u32>(i - 1);
            }

            for (const int prime_int : primes) {
                const u64 prime = static_cast<u64>(prime_int);
                const u64 composite = i * prime;
                if (composite > sieve_limit_) {
                    break;
                }

                is_composite[static_cast<std::size_t>(composite)] = 1;
                if (i % prime == 0) {
                    phi_[static_cast<std::size_t>(composite)] =
                        static_cast<u32>(phi_[static_cast<std::size_t>(i)] * prime);
                    break;
                }

                phi_[static_cast<std::size_t>(composite)] = static_cast<u32>(
                    static_cast<u64>(phi_[static_cast<std::size_t>(i)]) * (prime - 1));
            }
        }

        for (u64 i = 1; i <= sieve_limit_; ++i) {
            prefix_[static_cast<std::size_t>(i)] =
                prefix_[static_cast<std::size_t>(i - 1)] +
                static_cast<u64>(phi_[static_cast<std::size_t>(i)]);
        }
    }
};

class Euler432Solver {
public:
    explicit Euler432Solver(u64 n)
        : n_(n),
          prime_factors_(distinct_prime_factors(n)),
          phi_n_(euler_phi_u64(n)),
          totient_summatory_(kTotientSieveLimit) {}

    u128 solve(u64 m, bool allow_multithreading, unsigned requested_threads = 0) {
        std::vector<u64> smooth = generate_smooth_numbers(prime_factors_, m);

        std::vector<u64> quotients;
        quotients.reserve(smooth.size());
        for (const u64 value : smooth) {
            quotients.push_back(m / value);
        }

        std::vector<u64> unique_quotients = quotients;
        std::sort(unique_quotients.begin(), unique_quotients.end());
        unique_quotients.erase(std::unique(unique_quotients.begin(), unique_quotients.end()),
                               unique_quotients.end());

        std::unordered_map<u64, u128, U64Hash> sum_phi_by_quotient;
        sum_phi_by_quotient.reserve(unique_quotients.size() * 2 + 16);
        for (const u64 q : unique_quotients) {
            sum_phi_by_quotient.emplace(q, totient_summatory_.sum_phi(q));
        }

        const u128 inner = sum_over_quotients(quotients,
                                              sum_phi_by_quotient,
                                              allow_multithreading,
                                              requested_threads);
        return static_cast<u128>(phi_n_) * inner;
    }

private:
    u64 n_ = 0;
    std::vector<u64> prime_factors_;
    u64 phi_n_ = 0;
    TotientSummatory totient_summatory_;

    static u128 sum_over_quotients(const std::vector<u64>& quotients,
                                   const std::unordered_map<u64, u128, U64Hash>& sum_phi_by_quotient,
                                   bool allow_multithreading,
                                   unsigned requested_threads) {
        const unsigned threads =
            choose_thread_count(allow_multithreading, requested_threads, quotients.size());

        if (threads == 1) {
            u128 total = 0;
            for (const u64 q : quotients) {
                total += sum_phi_by_quotient.at(q);
            }
            return total;
        }

        std::vector<u128> partial(threads, 0);
        std::vector<std::thread> workers;
        workers.reserve(threads);

        for (unsigned tid = 0; tid < threads; ++tid) {
            workers.emplace_back([&, tid]() {
                const std::size_t left = quotients.size() * tid / threads;
                const std::size_t right = quotients.size() * (tid + 1) / threads;

                u128 local = 0;
                for (std::size_t i = left; i < right; ++i) {
                    local += sum_phi_by_quotient.at(quotients[i]);
                }
                partial[tid] = local;
            });
        }

        for (std::thread& worker : workers) {
            worker.join();
        }

        u128 total = 0;
        for (const u128 value : partial) {
            total += value;
        }
        return total;
    }
};

u128 brute_force_s(u64 n, u64 m) {
    u128 total = 0;
    for (u64 i = 1; i <= m; ++i) {
        total += euler_phi_u64(n * i);
    }
    return total;
}

bool parse_threads_argument(const std::string& arg, unsigned& threads) {
    constexpr const char* prefix = "--threads=";
    if (arg.rfind(prefix, 0) != 0) {
        return false;
    }

    const std::string value = arg.substr(std::char_traits<char>::length(prefix));
    if (value.empty()) {
        return false;
    }

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

    threads = parsed;
    return true;
}

bool run_validation_checkpoints(Euler432Solver& solver,
                                bool allow_multithreading,
                                unsigned requested_threads) {
    const std::vector<u64> brute_small = {1, 2, 5, 10, 100, 1'000, 10'000};

    for (const u64 m : brute_small) {
        const u128 fast = solver.solve(m, false, 1);
        const u128 brute = brute_force_s(kN, m);
        if (fast != brute) {
            std::cerr << "Brute-force checkpoint failed for m=" << m
                      << ": fast=" << to_string_u128(fast)
                      << ", brute=" << to_string_u128(brute) << '\n';
            return false;
        }
        std::cout << "Brute checkpoint S(510510, " << m << ") = "
                  << to_string_u128(fast) << " (ok)\n";
    }

    const u128 given = solver.solve(kCheckpointM, allow_multithreading, requested_threads);
    if (given != static_cast<u128>(kExpectedCheckpoint)) {
        std::cerr << "Given checkpoint failed for S(510510, 10^6): expected "
                  << kExpectedCheckpoint << ", got " << to_string_u128(given) << '\n';
        return false;
    }

    std::cout << "Given checkpoint S(510510, 10^6) = " << to_string_u128(given)
              << " (ok)\n";
    return true;
}

} // namespace

int main(int argc, char** argv) {
    bool allow_multithreading = true;
    unsigned requested_threads = 0;

    for (int i = 1; i < argc; ++i) {
        const std::string arg = argv[i];
        if (arg == "--single-thread") {
            allow_multithreading = false;
            continue;
        }
        if (!parse_threads_argument(arg, requested_threads)) {
            std::cerr << "Unknown argument: " << arg << '\n';
            std::cerr << "Usage: ./Euler432 [--single-thread] [--threads=N]\n";
            return 1;
        }
    }

    Euler432Solver solver(kN);
    if (!run_validation_checkpoints(solver, allow_multithreading, requested_threads)) {
        return 1;
    }

    const u128 answer = solver.solve(kTargetM, allow_multithreading, requested_threads);
    const u64 last_nine_digits = static_cast<u64>(answer % kLastDigitsMod);

    std::cout << "S(510510, 10^11) = " << to_string_u128(answer) << '\n';
    std::cout << "Last 9 digits: " << std::setw(9) << std::setfill('0') << last_nine_digits
              << '\n';
    std::cout << "Answer: " << to_string_u128(answer) << '\n';
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""
    answers = []
    equals = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answers.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equals.append(m2.group(1).strip())
    if answers:
        return answers[-1]
    if equals:
        return equals[-1]
    return lines[-1]


def should_skip_cpp_checkpoints(src: Path) -> bool:
    try:
        text = src.read_text(encoding="utf-8", errors="ignore")
    except OSError:
        return False
    return "--skip-checkpoints" in text


def run_cpp(binary: Path, src: Path, root: Path) -> str:
    cmd = [str(binary)]
    if should_skip_cpp_checkpoints(src):
        cmd.append("--skip-checkpoints")

    try:
        return subprocess.check_output(cmd, text=True, cwd=root)
    except subprocess.CalledProcessError:
        return subprocess.check_output(cmd, text=True, cwd=src.parent)


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = run_cpp(binary=binary, src=src, root=root)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


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

Java

import java.nio.file.*;
import java.util.*;
import java.util.regex.*;

public class Euler432 {
    private static final Pattern ANSWER_RE = Pattern.compile("answer\\s*:\\s*(.+)$", Pattern.CASE_INSENSITIVE);
    private static final Pattern EQUAL_RE = Pattern.compile("=\\s*(.+)$");

    private static String parseOutput(String stdout) {
        String[] lines = stdout.split("\\R");
        List<String> nonEmpty = new ArrayList<>();
        for (String line : lines) {
            String t = line.trim();
            if (!t.isEmpty()) {
                nonEmpty.add(t);
            }
        }
        if (nonEmpty.isEmpty()) {
            return "";
        }

        List<String> answers = new ArrayList<>();
        List<String> equals = new ArrayList<>();
        for (String line : nonEmpty) {
            Matcher m1 = ANSWER_RE.matcher(line);
            if (m1.find()) {
                answers.add(m1.group(1).trim());
            }
            Matcher m2 = EQUAL_RE.matcher(line);
            if (m2.find()) {
                equals.add(m2.group(1).trim());
            }
        }

        if (!answers.isEmpty()) {
            return answers.get(answers.size() - 1);
        }
        if (!equals.isEmpty()) {
            return equals.get(equals.size() - 1);
        }
        return nonEmpty.get(nonEmpty.size() - 1);
    }

    private static String pickCompiler() throws Exception {
        for (String compiler : List.of("clang++", "g++")) {
            Process probe = new ProcessBuilder("bash", "-lc", "command -v " + compiler)
                    .redirectErrorStream(true)
                    .start();
            String out = new String(probe.getInputStream().readAllBytes());
            int rc = probe.waitFor();
            if (rc == 0 && !out.trim().isEmpty()) {
                return compiler;
            }
        }
        throw new RuntimeException("No C++ compiler found (clang++/g++).");
    }

    private static Path cppSource(Path root) {
        return root.resolve("solutionsCpp").resolve("Euler432.cpp");
    }

    private static boolean shouldSkipCheckpoints(Path root) {
        Path src = cppSource(root);
        try {
            String text = Files.readString(src);
            return text.contains("--skip-checkpoints");
        } catch (Exception ex) {
            return false;
        }
    }

    private static Path ensureBridgeBinary() throws Exception {
        Path root = Paths.get(System.getProperty("user.dir"));
        Path src = cppSource(root);
        Path bin = root.resolve("solutionsCpp").resolve(".euler432_java_bridge");

        boolean rebuild = Files.notExists(bin)
                || Files.getLastModifiedTime(src).compareTo(Files.getLastModifiedTime(bin)) > 0;

        if (rebuild) {
            String compiler = pickCompiler();
            Process compile = new ProcessBuilder(
                    compiler,
                    "-std=c++17",
                    "-O2",
                    src.toString(),
                    "-o",
                    bin.toString())
                    .inheritIO()
                    .start();
            if (compile.waitFor() != 0) {
                throw new RuntimeException("Failed to compile Euler432 C++ bridge.");
            }
        }

        return bin;
    }

    private static String runBridge(Path bin, Path root, Path srcDir) throws Exception {
        List<String> cmd = new ArrayList<>();
        cmd.add(bin.toString());
        if (shouldSkipCheckpoints(root)) {
            cmd.add("--skip-checkpoints");
        }

        Process first = new ProcessBuilder(cmd)
                .directory(root.toFile())
                .redirectErrorStream(true)
                .start();
        String out = new String(first.getInputStream().readAllBytes());
        int rc = first.waitFor();
        if (rc == 0) {
            return out;
        }

        Process second = new ProcessBuilder(cmd)
                .directory(srcDir.toFile())
                .redirectErrorStream(true)
                .start();
        String out2 = new String(second.getInputStream().readAllBytes());
        int rc2 = second.waitFor();
        if (rc2 == 0) {
            return out2;
        }

        throw new RuntimeException("Euler432 C++ bridge failed.\n" + out + "\n" + out2);
    }

    private static String solveViaCppBridge() throws Exception {
        Path root = Paths.get(System.getProperty("user.dir"));
        Path src = cppSource(root);
        Path bin = ensureBridgeBinary();
        String out = runBridge(bin, root, src.getParent());
        String parsed = parseOutput(out);
        if (parsed.isEmpty()) {
            throw new RuntimeException("Euler432 C++ bridge produced empty output.");
        }
        return parsed;
    }

    public static void main(String[] args) throws Exception {
        System.out.println(solveViaCppBridge());
    }
}