Jiaqi's Blog

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

From Jiaqi's Blog

http://abclocal.go.com/wls/story?section=news/local/mathie&id=8443324

I don't have desire to join Black Friday shopping in early morning anymore, not in last 7 years, not a little bit. Things I bought from 2004 Black Friday are still in sealed boxes. This Thanksgiving, my biggest hope is to stay at home, completely forget about work, and take a long 4 days break with satisfying sleeps. Really want to do it this time.

Reality emerges in unfortunate way. At 3AM, my IPhone jumped up indicating a text message was received. There can be so many reasons for a text message on 3AM, sales promotion,wrong number, payment due, or I'm paged. I kept fingers crossed in dream and hoped it was not the last one. A few seconds later pager beeped. Instead of any of the other reasons, it really was because someone paged me. Finger crossing continue to prove in vain.

Walking to computer in pajama,  I opened two red eyes and read, "blah blah blah... to draw someone's attention, I escalated this ticket". No English words I learned could describe my mood at this point. The author of ticket decided to wake me up on 3AM Black Friday morning. not because system is in trouble, not because release is blocked, but to "draw attention". In a different fine day I would reply with a bunch of links to condition of ticket escalation and cc every manager. However now everything was pointless, I was already awake.

Ticket was nothing but a question of a well known issue, which should never, never be escalated, except that my foreign colleagues believe paging people is an effective way of communication as they live in a different timezone.

Done with work, I ran into sleep trouble again. The moment eyes are closed, all worries come to my mind. What if people recognize technical debt more seriously and decided to deal with problem earlier, what if I work for a different project, or a different company without on call, what if I'm a movie director instead of programmer, what if, what if... Brain spins so fast like Turbo key is pressed.

4:30 AM, just about the time I went over most of "what if" questions, wife called. "Honey I got this sweet deal we always wanted and you should go to Sam's Club in Seattle and get one as well". Indeed it is the deal I always want. My wife spent Thank Giving with her family this year and I'm left alone in Seattle. She brought the entire platoon to shop, which is total reasonable. With family, Black Friday shopping can be a lot of fun. The only gotcha is, she is in Indiana under Eastern timezone. "That's sweet." I murmured, "But it's really early and I prefer to sleep, so I'll skip".

5:00 AM, wife called again. "Great news, I can get one for you here in Indiana. Just tell me the SimCard number. You can take out SimCard with a needle...". So a project started. A project involving sweep of entire 3 bedroom condo to look for a needle, some handcraft, picture taking and emailing started at 5AM. Once I'm done with that, sky started showing light.

It's about 5:20 AM. I've never seen Seattle at 5AM, I don't even know the existence of 5AM in Seattle. It is stunning. After a series of crazy events which completely destroyed my hope for sleep, why not another crazy event, like going out and take photos.



Yet again, after 7 years I got up early in Black Friday morning. Plan is kaput, eyes are sore. Family is thousands mines away, and refrigerator is empty. However bad things pass and good things stay. Looking at these pictures, I am happy in the morning of Black Friday.

Cyclic number, 1/7 specifically, is something amazed me while I was a child. However I never really thought about cyclic numbers other than 1/7 until this problem. I decided to spend an evening researching and resolving the latest Project Euler problem, #358 Cyclic Number.

To solve this problem, we need an integer number X satisfying following criteria based on my understanding of cyclic number:
1. 1/X starts with 0.00000000137
2. X is dividable by 10^X-1
3. The result of (10^X-1/X) ends with 56789
4. X is a prime number
5. ?

I put a question mark for the fifth criterion because I haven't figured out what it is, while only with four others, the problem can almost be solved.

The first hint limits candidates between 724637681 and 729927007. Given the second and third hint, the last 5 digits of 56789 * X should be 99999, which means 56789 * (X-1) ends with 43210. X must ends with 09891 to satisfy such requirement. There are 53 numbers within range and ends with 09891, in which only 3 are prime numbers, 725509891, 726509891 and 729809891. The final answer hides in these three numbers.

All these three numbers meets requirement 2. I tried answering them to projecteuler and found the last one is correct answer. However I haven't figure out how to filter out two others programmatically. This still bothers me.

The Java code is in GitHub. It's quite efficient as far as I can tell. Most of the time is spent on prime number checking.

>>>>>> Runnining solution of problem 358
Last five digits result is 9891
Searching numbers between 724637681 and 729927007
Checking candidate: 725509891 with sum of digits 3264794505
Checking candidate: 726509891 with sum of digits 3269294505
Checking candidate: 729809891 with sum of digits 3284144505
53 numbers are verified
<<<<<< Solution 358 took 878.149399 ms