Problem 359: Hilbert's New Hotel

View on Project Euler

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

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.

Step 2: Floor Invariants Used by the Code

The C++, Python, and Java solutions all use two floor-specific constants:

$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$

$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$

The first few floor starters are \(1,2,4,8,12,18,24,\dots\), exactly matching \(\left\lfloor f^2/2\right\rfloor\). These identities are the nontrivial hotel-specific input to person_in_room. The C++ file does not assume them blindly: it greedily simulates the first 30000 arrivals and verifies that the closed form matches every populated entry \(P(f,r)\) for \(f,r\le 60\).

Given \(A_f\), the second room is forced to be

$$P(f,2)=s_f^2-A_f.$$

Because room numbers increase with arrival order, we need \(P(f,2) > A_f\), equivalently \(s_f^2 > 2A_f\). With \(A_f=\lfloor f^2/2\rfloor\), the smallest valid square root is therefore \(f\) on odd floors and \(f+1\) on even floors, exactly as in the code.

Step 3: Closed Form for All Rooms

Starting from \(p_1=A_f\), the recurrence gives

$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$

$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$

Subtracting terms two steps apart removes the alternating dependency:

$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$

$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$

So the odd-indexed rooms and even-indexed rooms each follow their own arithmetic-difference pattern. Summing those differences yields the formulas used by every implementation:

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

$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$

For \(f=1\), these collapse to the triangular numbers \(1,3,6,10,\dots\), which matches the simulated first floor exactly.

Step 4: Worked Checkpoints

For \(f=10\), we have \(A_{10}=10^2/2=50\) and \(s_{10}=11\). Since room \(20\) is even, \(k=10\), so

$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$

This is one of the explicit checkpoints in the C++ validator. The same file also checks the sample product \(N=20\):

$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$

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

That equality appears directly in run_checkpoints(), so the mathematical derivation and the implementation agree on both room formulas and the divisor-pair summation.

How the Code Works

The C++ solver is the authoritative implementation. It computes \(\lfloor\sqrt{N}\rfloor\) with a corrected integer-square-root routine, loops over every divisor candidate \(d\le \lfloor\sqrt{N}\rfloor\), and whenever \(d\mid N\) it adds \(P(d,N/d)\) and, if \(d\ne N/d\), also \(P(N/d,d)\). This matches the ordered-factor-pair definition of \(S(N)\).

The function person_in_room evaluates the formulas above in \(O(1)\) time using unsigned __int128 so that intermediate values cannot overflow. The Python file is a direct translation of the same logic with Python integers. The Java file deliberately does not duplicate the mathematics; it compiles and runs the C++ solver as a bridge, then parses the final number from the program output.

Before printing the target result, the C++ program validates base cases, the checkpoints \(P(10,20)=440\), \(P(25,75)=4863\), \(P(99,100)=19454\), the sample sum \(S(20)=608\), and a brute-force simulation of the first 30000 arrivals. That validation layer is why the closed form can be trusted as the source of truth for the HTML explanation.

Complexity Analysis

Evaluating a single \(P(f,r)\) is \(O(1)\) time and \(O(1)\) memory. The complete solver, as written in the local source files, tests every integer \(d\) from \(1\) to \(\lfloor\sqrt{N}\rfloor\), so the overall running time is \(O(\sqrt{N})\) and the memory usage is \(O(1)\).

For the actual target,

$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$

So only \(364\) ordered factor pairs contribute to the sum, even though the implementation reaches them by scanning all candidates up to

$$\left\lfloor\sqrt{N}\right\rfloor=8445638.$$

That is still small enough for an immediate computation in all three language variants.

Footnotes and References

  1. Problem page: https://projecteuler.net/problem=359
  2. Hilbert's hotel background: Wikipedia — Hilbert's paradox of the Grand Hotel
  3. Square numbers: Wikipedia — Square number
  4. Divisor-count function: Wikipedia — Divisor function
  5. Arithmetic progressions and finite differences: Wikipedia — Arithmetic progression

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());
    }
}