Problem 359: Hilbert's New Hotel

Project Euler Problem 359 Solution

EulerSolve provides an optimized solution for Project Euler Problem 359, Hilbert's New Hotel, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary People arrive in the order $1,2,3,\dots$. Each new person is placed on the lowest possible floor, and in the first empty room of that floor, such that the sum with the previous occupant on that floor is a perfect square. If $P(f,r)$ denotes the occupant of floor $f$, room $r$, then the target is $$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$ for $N=71328803586048$, with only the last eight digits required. The local solutions all reduce this to a closed formula for $P(f,r)$ together with a divisor scan. Mathematical Approach Step 1: Fix One Floor For a fixed floor $f$, write $p_t=P(f,t)$. Once the first square root used on that floor is $s_f$, the greedy hotel rule forces consecutive room pairs to sum to consecutive squares: $$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$ So room $1$ and room $2$ sum to $s_f^2$, room $2$ and room $3$ sum to $(s_f+1)^2$, room $3$ and room $4$ sum to $(s_f+2)^2$, and so on. This recurrence is the structural core of the implementation....

Detailed mathematical approach

Problem Summary

An infinite hotel has floors $1,2,3,\dots$, each with rooms $1,2,3,\dots$, and starts empty. People $1,2,3,\dots$ arrive in order, and person $n$ takes the first vacant room on the lowest-numbered floor that is either empty, or whose latest occupant $m$ makes $m+n$ a perfect square. Person $1$ opens floor $1$, person $2$ opens floor $2$ because $1+2=3$ is not a square, and person $3$ joins floor $1$ because $1+3=4$. Writing $P(f,r)$ for the person in room $r$ of floor $f$, and $0$ for a vacant room, the statement gives $P(1,1)=1$, $P(1,2)=3$, $P(2,1)=2$, $P(10,20)=440$, $P(25,75)=4863$ and $P(99,100)=19454$. We must add $P(f,r)$ over all pairs of positive integers with $fr=71328803586048$ and report the last eight digits of that sum. ^[1] The name recalls Hilbert's hotel, but that thought experiment shuffles guests around a full hotel; here an empty one is filled once and for all. ^[2]

The whole solution in one sentence: on every floor each occupant is followed by the smallest larger person whose sum with them is a perfect square, so the floors are exactly the chains of that single rule, these chains begin at person $1$ and at the people $n$ for which $2n$ or $2n+1$ is a perfect square, and the closed formula for $P(f,r)$ that follows is added over the $364$ divisor pairs of the product.

Mathematical Approach

We watch the rule act on twelve people, which suggests a floor is a chain built by one step; we define it, prove the hotel follows it, read a constant-time formula for $P(f,r)$ off the chain, and only then look at the product.

1. The first twelve people

Each line lists the sums person $n$ tries, floor by floor.

$1$: floor $1$ is empty, so room $1$ there.
$2$: $1+2=3$; floor $2$ is empty.
$3$: $1+3=4$, so room $2$ of floor $1$.
$4$: $3+4=7$, $2+4=6$; floor $3$ is empty.
$5$: $3+5=8$, $2+5=7$, $4+5=9$, so room $2$ of floor $3$.
$6$: $3+6=9$, so room $3$ of floor $1$.
$7$: $6+7=13$, $2+7=9$, so room $2$ of floor $2$.
$8$: $6+8=14$, $7+8=15$, $5+8=13$; floor $4$ is empty.
$9$: $6+9=15$, $7+9=16$, so room $3$ of floor $2$.
$10$: $6+10=16$, so room $4$ of floor $1$.
$11$: $10+11=21$, $9+11=20$, $5+11=16$, so room $3$ of floor $3$.
$12$: the four sums $22,21,23,20$ all fail, so floor $5$ opens.

The first five floors read $1,3,6,10,\dots$; $2,7,9,16,\dots$; $4,5,11,14,\dots$; $8,17,19,30,\dots$; $12,13,23,26,\dots$. Two patterns stand out: the floor openers are $1,2,4,8,12,18,24,32,40,50,\dots$, and neighbouring occupants sum not merely to squares but to consecutive squares, $9,16,25,36,\dots$ on floor $2$ and $4,9,16,25,\dots$ on floor $1$. Both come from one map.

2. The square successor of a number

For a positive integer $m$, let $\sigma(m)$ be the smallest integer $n\gt m$ such that $m+n$ is a perfect square. The next occupant of $m$'s floor is one such larger partner, so $\sigma$ is the step to study, and it has a one-line formula. Put

$$c(m)=\lfloor\sqrt{2m}\rfloor+1,$$

the integer characterised by $(c-1)^2\le 2m\lt c^2$, where $\lfloor\sqrt{\cdot}\rfloor$ is the integer square root. ^[3] Asking $n\gt m$ is the same as asking $m+n\gt 2m$, and the smallest square exceeding $2m$ is exactly $c(m)^2$. Hence

$$\sigma(m)=c(m)^2-m,$$

and $\sigma(m)\gt m$ because $2m\lt c(m)^2$. For instance $\sigma(1)=3$, $\sigma(2)=7$, $\sigma(4)=5$ and $\sigma(8)=17$, with $c$ equal to $2,3,3,5$ — the pairs already seen in Section 1.

3. Why the squares are consecutive

Let $c=c(m)$ and $n=\sigma(m)=c^2-m$. Then $2n=2c^2-2m$, so $2m\lt c^2$ gives $2n\gt c^2$, while $(c-1)^2\le 2m$ gives

$$2n\le 2c^2-(c-1)^2=c^2+2c-1\lt (c+1)^2.$$

Therefore $c^2\le 2n\lt (c+1)^2$, that is $c(n)=c+1$. Each step of $\sigma$ advances the square by one, so along a chain $m,\sigma(m),\sigma^2(m),\dots$ the neighbouring sums are $c^2,(c+1)^2,(c+2)^2,\dots$ — the consecutive squares observed above.

4. The map $\sigma$ is injective

Suppose $\sigma(m)=n$ and write $c=c(m)$. Section 3 says $c(n)=c+1$, so $c$ is determined by $n$ alone, and then $m=c^2-n$ is too. Explicitly,

$$m=\bigl(c(n)-1\bigr)^2-n.$$

So a number has at most one $\sigma$-predecessor, and a formula gives it. This is what forbids two floors from competing for the same new person.

5. Which people start a floor

A person $n$ starts a chain exactly when the candidate $m=(c-1)^2-n$ of Section 4, with $c=c(n)$, is not legitimate. Legitimacy needs $m\ge 1$ and $c(m)=c-1$, the latter meaning $(c-2)^2\le 2m\lt (c-1)^2$. Substituting $2m=2(c-1)^2-2n$ gives

$$(c-1)^2\lt 2n\le c^2-2.$$

Since $(c-1)^2\le 2n\lt c^2$ holds by the definition of $c$, only two values of $2n$ are excluded: $2n=(c-1)^2$ and $2n=c^2-1$. The first says that $2n$ is a perfect square, the second that $2n+1$ is; in both cases the square is forced to be the one shown, again by $(c-1)^2\le 2n\lt c^2$. The side condition $m\ge1$ costs nothing once $c\ge 3$, because $2n\le c^2-2$ then already forces $n\le(c-1)^2-1$; for $c=2$ it rules out $n=1$, whose candidate $m=0$ is not a person. So a person $n\ge 2$ starts a new chain exactly when $2n$ or $2n+1$ is a perfect square, and $n=1$ starts one too.

Writing the two families out, $2n=(2j)^2$ gives $n=2j^2$ and $2n+1=(2j+1)^2$ gives $n=2j^2+2j$. Interleaved in increasing order, together with $1$, these are

$$1,\;2,\;4,\;8,\;12,\;18,\;24,\;32,\;40,\;50,\;\dots$$

exactly the floor openers of Section 1. Numbering them $A_1=1$, $A_2=2$, $A_3=4,\dots$, we get $A_{2j}=2j^2$ and $A_{2j+1}=2j^2+2j$ for $j\ge1$; equivalently $A_f=\lfloor f^2/2\rfloor$ for $f\ge2$, with $A_1=1$ the exception, so from $f=2$ on they are the terms of A007590. ^[4] They are strictly increasing, a fact used twice below.

6. The chains cover every person exactly once

Take any positive integer and walk backwards along $\sigma$: each step is unique by Section 4 and strictly decreases the number, since $\sigma(m)\gt m$. The walk must stop, and only at a number with no predecessor, that is at some $A_f$. So every positive integer lies on exactly one chain, and

$$Q(f,r)=\sigma^{\,r-1}(A_f)$$

is a bijection from the pairs $(f,r)$ of positive integers onto the positive integers. Because $\sigma(m)\gt m$, every chain is infinite.

7. The hotel follows the chains

We claim $P(f,r)=Q(f,r)$ for all $f,r\ge1$, by induction on the arriving person $n$, assuming people $1,\dots,n-1$ are seated exactly where $Q$ puts them.

The chain of a floor increases, so by the hypothesis the occupants of a non-empty floor $f$ are $Q(f,1),\dots,Q(f,r)$ for some $r$, and its latest occupant is $m=Q(f,r)$. Person $Q(f,r+1)$ has not arrived, so $Q(f,r+1)\ge n$. If $m+n$ is a square then, as $n\gt m$, the definition of $\sigma$ gives $n\ge\sigma(m)=Q(f,r+1)$, hence $n=Q(f,r+1)$. So a floor accepts person $n$ only when $n$ is the chain successor of its latest occupant, and by Section 6 at most one floor qualifies.

If $n=A_{f_0}$, no occupied floor accepts $n$. The openers increase, so floors $1,\dots,f_0-1$ are occupied while floor $f_0$ is still empty: person $n$ opens floor $f_0$ in room $1$, as $Q$ says. Otherwise $n=\sigma(m)$ with $m=Q(f_0,r_0-1)$. Every floor $f\lt f_0$ is occupied, since $A_f\lt A_{f_0}\le m\lt n$, and none accepts $n$, as that would force its latest occupant to be the unique $\sigma$-predecessor $m$, which sits on floor $f_0$. Floor $f_0$ does accept $n$, so it is the lowest such floor, and its first vacant room is $r_0$ — again what $Q$ says, closing the induction. The chains are infinite, so no room stays vacant and the value $0$ never occurs.

8. A closed formula for $P(f,r)$

Let $s_f=c(A_f)$ be the first square root used on floor $f$. From $2A_1=2$ we get $s_1=2$; from $2A_{2j}=(2j)^2$, $s_{2j}=2j+1$; from $(2j)^2\le 2A_{2j+1}\lt(2j+1)^2$, $s_{2j+1}=2j+1$. So $s_f=2$ for $f=1$, $s_f=f+1$ for even $f$, $s_f=f$ for odd $f\ge3$. Section 3 now gives, for every $r\ge1$,

$$P(f,r)+P(f,r+1)=(s_f+r-1)^2.$$

Subtracting two consecutive instances of this identity removes the alternation:

$$P(f,r+2)-P(f,r)=2s_f+2r-1.$$

Odd and even rooms therefore each advance by an arithmetic increment. The $k-1$ increments from room $1$ to room $2k-1$ run $2s_f+1,2s_f+5,\dots,2s_f+4k-7$, so they average $2s_f+2k-3$; those from room $2$ to room $2k$ average $2s_f+2k-1$. Multiplying each average by $k-1$ and adding $P(f,1)=A_f$ or $P(f,2)=s_f^2-A_f$ gives

$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),$$

$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),$$

for $k\ge1$; each value costs a handful of operations. On floor $1$ both branches collapse to $P(1,r)=r(r+1)/2$, the triangular numbers A000217. ^[5] Floor $2$ reads $2,7,9,16,20,29,\dots$, which is OEIS A107386 from its fifth term on, listed there with the recurrence $a(k)=(k-2)^2-a(k-1)$ for $k\ge4$ — the alternating identity in disguise. ^[6]

9. The three large checkpoints

Floor $10$ is even, so $A_{10}=50$, $s_{10}=11$, and room $20$ is even with $k=10$. Floor $25$ is odd: $A_{25}=312$, $s_{25}=25$, room $75$ odd with $k=38$. Floor $99$ is odd: $A_{99}=4900$, $s_{99}=99$, room $100$ even with $k=50$. The formulas give

$$\begin{aligned}P(10,20)&=71+9\cdot41=440,\\P(25,75)&=312+37\cdot123=4863,\\P(99,100)&=4901+49\cdot297=19454,\end{aligned}$$

matching the statement.

10. Summing over the divisor pairs

The quantity asked for is

$$S(N)=\sum_{fr=N}P(f,r),$$

the sum over the ordered pairs with product $N$, that is over the divisors $f$ of $N$ with $r=N/f$. For $N=20$ the pairs are $(1,20)$, $(2,10)$, $(4,5)$, $(5,4)$, $(10,2)$ and $(20,1)$, with $P(1,20)=20\cdot21/2=210$, $P(20,1)=\lfloor 400/2\rfloor=200$, $P(10,2)=11^2-50=71$, and in all

$$S(20)=210+67+34+26+71+200=608.$$

The target product factorises as

$$N=71328803586048=2^{27}\cdot3^{12},$$

so it has $\tau(N)=(27+1)(12+1)=364$ divisors, by the product formula for the number-of-divisors function, ^[7] and the sum has $364$ terms. The extreme ones, $P(N,1)=\lfloor N^2/2\rfloor$ and $P(1,N)=N(N+1)/2$, are $28$-digit numbers, far beyond $2^{64}\approx1.8\cdot10^{19}$. The exact sum occupies $93$ bits, so the programs accumulate in $128$-bit or arbitrary-precision arithmetic and report only its residue modulo $10^8$ — the last $8$ digits.

How the Code Works

isqrt_u64 computes $\lfloor\sqrt n\rfloor$ for $n\ge1$; at $n=0$ its second correction loop would divide by zero, but no call here passes $0$. It starts from a long double square root and corrects it with two loops comparing $r$ against $n/r$ rather than $r^2$ against $n$, so no intermediate product can overflow; on return $r^2\le n\lt(r+1)^2$. ^[3] It serves the divisor scan and the self-check's perfect-square test.

person_in_room(floor, room) is Section 8 verbatim. It sets first_person to $A_f$ — $1$ for floor $1$, floor*floor/2 otherwise — and first_square_root to $s_f$, namely $2$ for floor $1$, the floor number for odd floors and one more for even floors; a parity test on room picks the odd or even branch with $k$ as there. first_person, $k$, the return value and the running total are unsigned __int128, a GCC and Clang extension, while the arguments, first_square_root and the loop variables stay std::uint64_t; casts widen the operands before the large products are formed, since single terms already exceed $64$ bits. ^[8]

sum_for_product_last8(product) walks $d$ from $1$ to $\lfloor\sqrt{\mathrm{product}}\rfloor$, skips non-divisors, and for each divisor $d$ with cofactor $q$ adds person_in_room(d, q) and, unless $d=q$, person_in_room(q, d) — each ordered pair once. The total is reduced modulo $10^8$ only at the end.

validate_formula_against_simulation is an independent brute force: tops holds each floor's latest occupant and floors the full lists, $30000$ people are placed by scanning tops in order and testing each sum with isqrt_u64, and every entry with $f,r\le60$ is checked against person_in_room. run_checkpoints adds the six statement values and $S(20)=608$. main accepts only --skip-checkpoints, exiting with code $1$ on any other argument and $2$ on a failed check.

The Python file nests an isqrt wrapper on math.isqrt and a person_in_room inside solve, which also holds the divisor loop; it carries no checkpoint or simulation routine, and Python's integers remove every width question. ^[9] The Java file repeats none of the mathematics: it expects solutionsCpp/Euler359.cpp relative to the working directory, compiles it with the first available of clang++ and g++ whenever the cached binary is missing or older than the source, runs it, and reads the last line matching answer:, else the last with =, else the last non-empty line — the case here. One detail is worth knowing: shouldSkipCheckpoints searches the C++ source text for the literal --skip-checkpoints, which the argument parser of that very source contains, so the bridge always starts with the flag and the Java route never re-runs the checks.

Complexity and Verification

Evaluating $P(f,r)$ is $O(1)$ in time and memory. The divisor scan dominates: it tests every $d\le\lfloor\sqrt N\rfloor=8445638$, so the method as written is $O(\sqrt N)$ time and $O(1)$ memory. Of those candidates $182$ divide this non-square $N$, each giving two ordered pairs — the $364$ terms. Once the prime factorisation is known, generating the divisors from the exponents and evaluating them costs only $O(\tau(N))$, though finding that factorisation costs separately; the scan is kept because it needs none. The brute-force check is the slowest part of a full run: it opens $244$ floors while placing $30000$ people and, stopping at the first floor that fits, performs $2463056$ square tests rather than the $4884025$ of a full sweep, plus a few hundred kilobytes for the occupant lists.

The packaged checks are the six statement values, $S(20)=608$, and the $3600$ comparisons on the $60\times60$ grid, which a simulation of $30000$ arrivals fills completely, so none is silently skipped. The following were verified independently here.

A fresh simulation of $40000$ arrivals, building $282$ floors, agrees with the closed formula on all $40000$ placements.
$\sigma(m)=c(m)^2-m$ agrees with a direct search for the smallest larger partner for every $m\le20000$, and $c(\sigma(m))=c(m)+1$ and injectivity hold for every $m\le200000$.
The $100$ integers $n\le5000$ missed by $\sigma$ are exactly $1$ and the values $\lfloor f^2/2\rfloor\le5000$ with $f\ge2$; for $2\le n\le5000$, being missed is equivalent to $2n$ or $2n+1$ being square.
The chains $\sigma^{\,r-1}(A_f)$ reproduce the formula for all $f,r\le399$; $P(2,r)$ matches $46$ published terms of A107386; and $S(M)$ from the formula equals the simulated sum for all $282$ products $M\le500$ whose divisor pairs lie inside the simulated region.

The C++ and Python programs print byte-identical output for the requested product. Timed on one desktop machine, with the C++ built at -O2 and Python 3.11, the full C++ run including its checks takes about $0.01$ seconds and the Python solve() about $0.17$ seconds.

Footnotes and References

The references below supply the background facts and catalogued sequences used above. The map $\sigma$, its injectivity, the characterisation of the floor openers and the proof that the hotel follows the chains are derived explicitly here.

Project Euler 359 — Hilbert's New Hotel. The official statement gives the seating rule above, works out persons 1 to 3, lists P(1,1) = 1, P(1,2) = 3, P(2,1) = 2, P(10,20) = 440, P(25,75) = 4863, P(99,100) = 19454, and asks for the last 8 digits of the sum of P(f, r) over all f × r = 71328803586048.
Wikipedia — Hilbert's paradox of the Grand Hotel. In Hilbert's thought experiment every room of an endless hotel is already full, yet moving each guest from room n to room n + 1 frees one room and moving each to room 2n frees infinitely many. It credits Hilbert's 1924–1925 lecture "Über das Unendliche"; the hotel here borrows only the name.
Wikipedia — Integer square root. It defines the integer square root as the greatest integer not exceeding the square root and characterises it by x² ≤ y < (x + 1)² — the property that pins down c(m) in Sections 2 and 5 and that the C++ correction loops restore after the floating-point estimate.
OEIS A007590. The sequence a(n) = ⌊n²/2⌋, with terms 0, 0, 2, 4, 8, 12, 18, 24, 32, 40, 50, 60, 72, 84, 98, …, which from n = 2 on lists the people who open a new floor (Section 5).
OEIS A000217. The triangular numbers n(n + 1)/2, with terms 0, 1, 3, 6, 10, 15, 21, 28, …. Floor 1 holds exactly these from the second term on, both branches of Section 8 collapsing to r(r + 1)/2 there.
OEIS A107386. It lists 0, 1, 1, 2, 2, 7, 9, 16, 20, 29, 35, 46, 54, 67, … with the recurrence a(n) = (n − 2)² − a(n − 1) for n ≥ 4. From its fifth term on it is the occupant list of floor 2, and that recurrence is the consecutive-square identity.
Wikipedia — Divisor function. The number-of-divisors function σ₀, also written d(n) or τ(n), equals the product of the aᵢ + 1 over the exponents of the prime factorisation; for 2²⁷ · 3¹² it gives the 364 ordered factor pairs of Section 10.
GCC manual — 128-bit integers. __int128 and unsigned __int128 are available on targets with an integer mode wide enough to hold 128 bits, which the C++ solution relies on for its 28-digit terms.
Python documentation — math.isqrt. It returns the integer square root of a non-negative integer and was added in Python 3.8. The immutable C++ revision Euler359.cpp holds isqrt_u64, person_in_room, sum_for_product_last8 and the checks, and is the implementation record here.

Problem 359 source code

C++

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

namespace {

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

constexpr u64 kTargetProduct = 71328803586048ULL;
constexpr u64 kMod = 100000000ULL;

u64 isqrt_u64(const u64 n) {
    u64 r = static_cast<u64>(std::sqrt(static_cast<long double>(n)));
    while ((r + 1ULL) <= n / (r + 1ULL)) {
        ++r;
    }
    while (r > n / r) {
        --r;
    }
    return r;
}

u128 person_in_room(const u64 floor, const u64 room) {
    u128 first_person = 0;
    u64 first_square_root = 0;

    if (floor == 1ULL) {
        first_person = 1;
        first_square_root = 2;
    } else {
        first_person = (static_cast<u128>(floor) * floor) / 2U;
        first_square_root = (floor & 1ULL) ? floor : (floor + 1ULL);
    }

    if ((room & 1ULL) != 0ULL) {
        const u128 k = (room + 1ULL) / 2ULL;
        return first_person + (k - 1U) * (2U * static_cast<u128>(first_square_root) + 2U * k - 3U);
    }

    const u128 k = room / 2ULL;
    return static_cast<u128>(first_square_root) * first_square_root - first_person +
           (k - 1U) * (2U * static_cast<u128>(first_square_root) + 2U * k - 1U);
}

u64 sum_for_product_last8(const u64 product) {
    const u64 root = isqrt_u64(product);
    u128 total = 0;

    for (u64 d = 1; d <= root; ++d) {
        if (product % d != 0ULL) {
            continue;
        }
        const u64 q = product / d;
        total += person_in_room(d, q);
        if (d != q) {
            total += person_in_room(q, d);
        }
    }

    return static_cast<u64>(total % kMod);
}

bool validate_formula_against_simulation() {
    const u64 people_limit = 30000ULL;
    std::vector<u64> tops;
    std::vector<std::vector<u64>> floors;
    tops.reserve(512);
    floors.reserve(512);

    for (u64 person = 1; person <= people_limit; ++person) {
        bool placed = false;
        for (std::size_t i = 0; i < tops.size(); ++i) {
            const u64 s = tops[i] + person;
            const u64 r = isqrt_u64(s);
            if (r * r == s) {
                tops[i] = person;
                floors[i].push_back(person);
                placed = true;
                break;
            }
        }
        if (!placed) {
            tops.push_back(person);
            floors.push_back({person});
        }
    }

    for (u64 f = 1; f <= 60; ++f) {
        if (f > floors.size()) {
            break;
        }
        for (u64 r = 1; r <= 60; ++r) {
            if (floors[static_cast<std::size_t>(f - 1ULL)].size() < r) {
                break;
            }
            const u64 brute = floors[static_cast<std::size_t>(f - 1ULL)][static_cast<std::size_t>(r - 1ULL)];
            const u64 fast = static_cast<u64>(person_in_room(f, r));
            if (brute != fast) {
                std::cerr << "Checkpoint failed: mismatch at floor " << f << ", room " << r << '\n';
                return false;
            }
        }
    }
    return true;
}

bool run_checkpoints() {
    if (person_in_room(1ULL, 1ULL) != 1U || person_in_room(1ULL, 2ULL) != 3U || person_in_room(2ULL, 1ULL) != 2U) {
        std::cerr << "Checkpoint failed: base examples\n";
        return false;
    }

    if (person_in_room(10ULL, 20ULL) != 440U) {
        std::cerr << "Checkpoint failed: P(10,20)\n";
        return false;
    }
    if (person_in_room(25ULL, 75ULL) != 4863U) {
        std::cerr << "Checkpoint failed: P(25,75)\n";
        return false;
    }
    if (person_in_room(99ULL, 100ULL) != 19454U) {
        std::cerr << "Checkpoint failed: P(99,100)\n";
        return false;
    }

    if (sum_for_product_last8(20ULL) != 608ULL) {
        std::cerr << "Checkpoint failed: sum for product 20\n";
        return false;
    }

    if (!validate_formula_against_simulation()) {
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    bool skip_checkpoints = false;
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            skip_checkpoints = true;
        } else {
            std::cerr << "Unknown argument: " << arg << '\n';
            return 1;
        }
    }

    if (!skip_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const u64 answer = sum_for_product_last8(kTargetProduct);
    std::cout << answer << '\n';
    return 0;
}

Python

import math

def solve():
    TARGET_PRODUCT = 71328803586048
    MOD = 100_000_000

    def isqrt(n):
        return math.isqrt(n)

    def person_in_room(floor, room):
        if floor == 1:
            first_person = 1
            first_sq_root = 2
        else:
            first_person = (floor * floor) // 2
            first_sq_root = floor if floor & 1 else floor + 1

        if room & 1:  # odd room
            k = (room + 1) // 2
            return first_person + (k - 1) * (2 * first_sq_root + 2 * k - 3)
        else:  # even room
            k = room // 2
            return first_sq_root * first_sq_root - first_person + (k - 1) * (2 * first_sq_root + 2 * k - 1)

    root = isqrt(TARGET_PRODUCT)
    total = 0
    for d in range(1, root + 1):
        if TARGET_PRODUCT % d != 0:
            continue
        q = TARGET_PRODUCT // d
        total += person_in_room(d, q)
        if d != q:
            total += person_in_room(q, d)

    return str(total % MOD)

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

Java

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

public class Euler359 {
    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("Euler359.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(".euler359_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 Euler359 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("Euler359 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("Euler359 C++ bridge produced empty output.");
        }
        return parsed;
    }

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