Project Euler Problem 359

Project Euler Problem 359

Solution

Answer: 40632119

Let

$$P(f,r)$$

be the person occupying room $r$ on floor $f$.

We must compute

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

and return the last $8$ digits.

---

1. Mathematical analysis

Step 1: Structure of a floor

Suppose a floor starts with person $a$. Let the occupants be

$$x_1=a,\ x_2,\ x_3,\dots$$

By construction, consecutive occupants satisfy

$$x_n+x_{n+1}=k_n^2$$

for a sequence of consecutive squares.

From the examples:

• Floor 1: $1,3,6,10,\dots$

$$1+3=2^2,\quad 3+6=3^2,\quad 6+10=4^2$$

• Floor 2: $2,7,9,16,\dots$

$$2+7=3^2,\quad 7+9=4^2,\quad 9+16=5^2$$

• Floor 3: $4,5,11,14,\dots$

$$4+5=3^2,\quad 5+11=4^2,\quad 11+14=5^2$$

Thus each floor has a starting square index $s$, and:

$$x_{n+1}=(s+n-1)^2-x_n$$

---

Step 2: First occupant of each floor

Experimenting with the first room of each floor gives:

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

This follows the pattern

$$P(f,1)=\left\lfloor \frac{f^2}{2}\right\rfloor$$

(for $f=1$, this gives $0$, so floor 1 is a special case).

Also:

• odd floors use $s=f$,
• even floors use $s=f+1$.

So for $f>1$,

$$a=\left\lfloor \frac{f^2}{2}\right\rfloor, \qquad s= \begin{cases} f & f\text{ odd}\ f+1 & f\text{ even} \end{cases}$$

---

Step 3: Closed form for $P(f,r)$

Solving the recurrence gives:

For odd room $r=2m-1$,

$$P(f,r) = a+(m-1)(2s+2m-3)$$

For even room $r=2m$,

$$P(f,r) = -a+(s+m-1)^2+m(m-1)$$

These formulas reproduce all examples:

• $P(10,20)=440$
• $P(25,75)=4863$
• $P(99,100)=19454$

exactly.

---

Step 4: Divisors to sum over

We need all positive integer pairs $(f,r)$ with

$$fr=71328803586048$$

Factorization:

$$71328803586048 = 2^{27}3^{12}$$

So every divisor is

$$f=2^a3^b \quad (0\le a\le 27,\ 0\le b\le 12)$$

and

$$r=\frac{N}{f}$$

There are

$$(27+1)(12+1)=364$$

such pairs.

We sum $P(f,r)$ over all of them modulo $10^8$.

---

2. Python implementation

from math import prod

MOD = 10**8
N = 71328803586048

def P(f, r):
    """Return P(f, r)."""

    # Floor 1 is special
    if f == 1:
        a = 1
        s = 2
    else:
        a = (f * f) // 2
        s = f if (f % 2 == 1) else (f + 1)

    if r % 2 == 1:
        # odd room: r = 2m - 1
        m = (r + 1) // 2
        return a + (m - 1) * (2 * s + 2 * m - 3)
    else:
        # even room: r = 2m
        m = r // 2
        return -a + (s + m - 1) ** 2 + m * (m - 1)

# Generate all divisors of N = 2^27 * 3^12
total = 0

for a in range(28):
    for b in range(13):
        f = (2 ** a) * (3 ** b)
        r = N // f
        total = (total + P(f, r)) % MOD

print(total)

---

3. Code walkthrough

1. P(f, r)

• Computes the first occupant:

$$a=\left\lfloor \frac{f^2}{2}\right\rfloor$$

• Chooses the starting square index $s$.
• Uses the closed form depending on parity of $r$.

2. Divisor generation

• Since

$$N=2^{27}3^{12},$$

every divisor is generated by choosing powers of 2 and 3. 3. Summation

• For each divisor $f$, compute

$$r=\frac{N}{f}$$

• Add $P(f,r)$ modulo $10^8$.

---

4. Final verification

The formula reproduces the problem’s sample values exactly:

$$P(10,20)=440$$

$$P(25,75)=4863$$

$$P(99,100)=19454$$

The divisor count is correct (364 total factor pairs), and modular arithmetic avoids unnecessary huge integers.

Answer: 40632119