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

Popular posts from this blog

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

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

A dozen things to know about AWS Simple Workflow in Eclipse and Maven

Amazon AWS Simple Workflow AWS Simple Workflow(SWF) from Amazon is a unique workflow solution comparing to traditional workflow products such as JBPM and OSWorkflow. SWF is extremely scalable and engineer friendly(in that flow is defined with Java code) while it comes with limitations and lots of gotchas. Always use Flow Framework The very first thing to know is, it's almost impossible to build a SWF application correctly without Flow Framework . Even though the low level SWF RESTful service API is public and available in SDK, for most workflow with parallelism, timer or notification, consider all possibilities of how each event can interlace with another, it's beyond manageable to write correct code with low-level API to cover all use cases. For this matter SWF is quite unique comparing to other thin-client AWS technologies. The SWF flow framework heavily depends on AspectJ for various purposes. If you are not familiar with AspectJ in Eclipse and Maven, this article