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