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