Skip to main content

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
Labels:

Comments

Post a Comment

Popular posts from this blog

Customize IdGenerator in JPA, gap between Hibernate and JPA annotations

JPA annotation is like a subset of Hibernate annotation, this means people will find something available in Hibernate missing in JPA. One of the important missing features in JPA is customized ID generator. JPA doesn't provide an approach for developer to plug in their own IdGenerator. For example, if you want the primary key of a table to be BigInteger coming from sequence, JPA will be out of solution. Assume you don't mind the mixture of Hibernate and JPA Annotation and your JPA provider is Hibernate, which is mostly the case, a solution before JPA starts introducing new Annotation is, to replace JPA @SequenceGenerator with Hibernate @GenericGenerator. Now, let the code talk. /** * Ordinary JPA sequence. * If the Long is changed into BigInteger, * there will be runtime error complaining about the type of primary key */ @Id @Column(name = "id", precision = 12) @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "XyzIdGenerator") @SequenceGe...
4 comments
Read more

Spring, Angular and other reasons I like and hate Bazel at the same time

For several weeks I've been trying to put together an Angular application served Java Spring MVC web server in Bazel. I've seen the Java, Angular combination works well in Google, and given the popularity of Java, I want get it to work with open source. How hard can it be to run arguably the best JS framework on a server in probably the most popular server-side language with  the mono-repo of planet-scale ? The rest of this post walks through the headaches and nightmares I had to get things to work but if you are just here to look for a working example, github/jiaqi/angular-on-java is all you need. https://github.com/jiaqi/angular-on-java Java web application with Appengine rule Surprisingly there isn't an official way of building Java web application in Bazel, the closest thing is the Appengine rule  and Spring MVC seems to work well with it. 3 Java classes, a JSP and an appengine.xml was all I need. At this point, the server starts well but I got "No ...
Post a Comment
Read more

1300ms to 160ms, tune Spring/Hibernate on slow MySQL

I write this article to remember the different behaviour various JDBC connection pool displays when they work with slow JDBC connection(to MySQL database, in this case). It starts with a typical Java application on Spring, Hibernate, Jetty, ApacheCXF and MySQL like following code. Version 1: without correct pooling //... service code @Transactional(isolation=Isolation.READ_COMMITTED) public void foo() { //... do something with database } //... connection pool configuration ... class = "com.mysql.jdbc.jdbc2.optional.MysqlConnectionPoolDataSource"; url = "jdbc:mysql://mysql.far-far-away.com/mysystem"; user = ... //... transaction management configuration in spring ... <tx:annotation-driven transaction-manager="transactionManager" order="100" /> <bean id="transactionManager" class="org.springframework.orm.hibernate3.HibernateTransactionManager"> <property name="sessionFactory" ref="mySessionFact...
2 comments
Read more