Project Euler 359 - Hilbert's New Hotel

Problem 359, Hilbert's new Hotel

Had no idea where to start at all, the only thing I could was to write a small program to print out first hundred numbers in naive way.

[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91]
[2, 7, 9, 16, 20, 29, 35, 46, 54, 67, 77, 92]
[4, 5, 11, 14, 22, 27, 37, 44, 56, 65, 79, 90]
[8, 17, 19, 30, 34, 47, 53, 68, 76, 93]
[12, 13, 23, 26, 38, 43, 57, 64, 80, 89]
[18, 31, 33, 48, 52, 69, 75, 94]
[24, 25, 39, 42, 58, 63, 81, 88]
[32, 49, 51, 70, 74, 95]
[40, 41, 59, 62, 82, 87]
[50, 71, 73, 96, 100]
[60, 61, 83, 86]
[72, 97, 99]
[84, 85]
[98]

As you may see, the result is very interesting. The numbers on the first column seems to be ( row + 1 ) / 2 * ( row / 2 ) * 2. Note that row/2*2 != row since all operations are integer operations.

If we calculate the delta values between consecutive numbers in each row, we got

 2, 3, 4, 5, 6, 7, 8, 9,10, 11, 12, 13, 

 5, 2, 7, 4, 9, 6,11, 8,13, 10, 15, 

 1, 6, 3, 8, 5,10, 7,12, 9, 14, 11, 

 9, 2,11, 4,13, 6,15, 8,17, 

 1,10, 3,12, 5,14, 7,16, 9, 

13, 2,15, 4,17, 6,19, 

 1,14, 3,16, 5,18, 7, 

17, 2,19, 4,21, 

 1,18, 3,20, 5, 

21, 2,23, 4, 

 1,22, 3, 

25, 2, 

1, 

Spot the pattern? There are several of them.

These pattern does apply to six known values donated by the original problem. Assume such pattern sustains all the way, it becomes trivial to implement a function returning P(f,r) with arbitrary f and r.  I had to use BigInteger instead of long in Java code as P can easily overflow long primitive.

Combinations of f and r is obvious since 71328803586048 = 2^27*3^12. Just for performance gain, I reused a class, BoundInteger, that I used for other problems earlier to calculate last 8 digits of integers without doing entire calculation. The whole program only takes 15ms, probably a solution that takes the least execution time comparing to other project euler problems.

I still spent a bit more than a day to get it right, mostly because overflow happens everywhere. Even the first number in a row or a number in the first row can easily overflow a Java long primitive. I had to use BigInteger everywhere.



Source Code