Skip to main content

Cyclic numbers - Project Euler problem 358



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

Comments

Post a Comment

Popular posts from this blog

Publish Maven site with Amazon S3 and CloudFront

Amazon S3 now supports static website hosting . As a 10 years Maven user, I wonder how easy it is to deploy Maven generated site to Amazon S3 and let the rock-solid storage provider to host my project websites. There are several existing s3 wagon providers , which all seem to have the same problem, not supporting directory copy. This is understandable since before S3 new website hosting feature, I guess people mostly expect to deploy artifacts rather than website to S3. So my first task is to write an AWS S3 wagon that supports directory copy. With AWS Java SDK , task becomes as simple as one single class . I made my S3 wagon available in Maven central repository at org.cyclopsgroup:awss3-maven-wagon:0.1 . The source code is hosted in github:jiaqi/cym2/awss3 . The next thing is to create an S3 bucket in console . To avoid trouble, bucket name is set to the future website domain name according to this discussion . Website feature needs to be explicitly enabled. I also created an...
5 comments
Read more

4-states state machine for CSV parsing

Parsing CSV file is easy, it's nothing but splitting string with comma delimiter, which can be easily done in Java... The first thing came to my mind when I'm about to parse CSV file in Java is just like that. Now, reality is that following examples are all possible valid lines in a CSV file 1,Bender 2,"Bender" 3,"Bender, Bending" 4,"Ben""d""er" 5, Ben"der 6, Ben""der Line 7 might be arguable but anyway, two basic rules are If there's comma in field, use double quot to wrap field, otherwise double quot wrapper isn't required. Inside double quot, double quot is used to escape double quot. Suddenly the problem is complicated to something more than string splitting, however it can be simplified into a finite state machine with 4 states. States: 1. Ready for new field (initial state) 2. Field without double quot 3. Field with double quot 4. Escaping or end of double quot Transitions *Direction*|*Condition*|*Ac...
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