and e

An infinite number of people (numbered 1, 2, 3, etc.) are lined up to get a room at Hilbert’s newest infinite hotel. The hotel contains an infinite number of floors (numbered 1, 2, 3, etc.), and each floor contains an infinite number of rooms (numbered 1, 2, 3, etc.).

Initially the hotel is empty. Hilbert declares a rule on how the n^th person is assigned a room: person n gets the first vacant room in the lowest numbered floor satisfying either of the following:

• the floor is empty
• the floor is not empty, and if the latest person taking a room in that floor is person m, then m + n is a perfect square

Person 1 gets room 1 in floor 1 since floor 1 is empty.
Person 2 does not get room 2 in floor 1 since 1 + 2 = 3 is not a perfect square.
Person 2 instead gets room 1 in floor 2 since floor 2 is empty.
Person 3 gets room 2 in floor 1 since 1 + 3 = 4 is a perfect square.

Eventually, every person in the line gets a room in the hotel.

Define P(f, r) to be n if person n occupies room r in floor f, and 0 if no person occupies the room. Here are a few examples:
P(1, 1) = 1 
P(1, 2) = 3 
P(2, 1) = 2 
P(10, 20) = 440 
P(25, 75) = 4863 
P(99, 100) = 19454

Find the sum of all P(f, r) for all positive f and r such that f * r = 71328803586048 and give the last 8 digits as your answer.

The fun part was finding P(f,r), the rest was just programming. I first filled in the hotel for the first fifty or so and looked for a pattern.

{“0”, “1”, “3”, “6”, “10”, “15”, “21”},
{“2”, “7”, “9”, “16”, “20”, “29”, “35”},
{“4”, “5”, “11”, “14”, “22”, “27”, “37”},
{“8”, “17”, “19”, “30”, “34”, “47”, “53”},
{“12”, “13”, “23”, “26”, “38”, “43”, “57”},
{“18”, “31”, “33”, “48”, “52”, “69”, “75”},
{“24”, “25”, “39”, “42”, “58”, “63”, “81”}

This is the first seven floors and seven rooms. Notice that I made the first room 0 instead of 1 (the pattern worked out better that way).

The first thing to notice is that the first floor is all the triangle numbers, that is the rth room is the sum of the first r integers. Now, if you group the next two floors together you can add one and subtract one from the elements to get triangle numbers again (this time shifted over by a constant factor). Looking at the next two floors, the same thing applies just with plus and minus 2 instead of 1. Using the floor and mod functions you can then determine P(f,r), (I will leave the complete derivation to you). In Mathematica this looks like:

P = 1/2*(#2 + 2*Floor[#1/2])*(#2 + 2*Floor[#1/2] - 1) +
   Floor[#1/2]*(2*Mod[#1 + #2 - 1, 2] - 1) &

This is using the pure functional form, so #1 = f and #2 = r and the & symbol is just telling the computer that it is a function.

Solving the rest of the problem was simply finding the factors of 71328803586048, applying P to each one and so on. Also the final solution requires the first room be 1, so there is a little bit of messiness there. Other than that is is pretty straight forward. (I got lazy with finding the factors so I just used Mathematica’s Solve feature to do the dirty work for me). Final solution:

P = 1/2*(#2 + 2*Floor[#1/2])*(#2 + 2*Floor[#1/2] - 1) +
   Floor[#1/2]*(2*Mod[#1 + #2 - 1, 2] - 1) &
sol = Solve[f r == 71328803586048 && f > 0 && r > 0, {f, r}, Integers];
Mod[Apply[Plus, P[f, r] /. sol] - P[1, 71328803586048] +
  P[1, 71328803586049], 10^8]