Reciprocal Cycles II
This problem is very similar to problem 26. But it is much harder than problem 26. Problem was posted in 2002 while this problem was posted in 2013!
I checked my code for problem 26. I just tried it for the largest prime number less than 1e8, which is 99999989; it has a recurring cycle of 99999988. It takes 1.3 second to find the recurring period for this prime number! So it is nearly impossible to use similar code to handle problem 417!
I tried problem 417 a while ago, all effort in vain. But today I found more than 300 people has already solved it. It should be relatively simple. I carefully checked the discussion thread for problem 26, then I found some gems in it. For example, a key word multiplicative order pops up. Some more useful information can also be found in the discussion. Finally, the problem is solved after I did some research from the Internet!
Recently, PE are more difficult to solve. For example, the run time of some clever approach is about 15 to 25 seconds. This almost ruled out the possibility of some semi-bruteforce approaches!
Showing posts with label multiplicative order. Show all posts
Showing posts with label multiplicative order. Show all posts
Sunday, August 4, 2013
Sunday, April 21, 2013
project euler problem 129 130 132 133
Repunit
Problem 129 is easy to brute force. Some observation is required to make this problem simple and easy. This problem is very closely related to problem 26.
Problem 130 is also very simple. If we do not care to use brute force, the result can be found in 20ms or so. But smq and hk extended the problem to the limit of 2500. The problem becomes extremely time costly. I tried the limit = 1000, needs 10 seconds. limit 2500 needs 79 second. I do not want to waste time to 2500 since it takes more than half an hour.
Problem 132 is quite simple if one reviewed the discussion thread of problem 129 and 130. I generated all primes up to 500K, and it just take 50ms to find the first forty prime factors. In the discussion thread, daniel.is.fischer asks the sum of prime factors below 1e9. I tried it, it is quite difficult, my code runs for near 6 minutes to get the answer. I did not figure out how they made it to 1 minute.
Problem 133 looks like quite different, but still the same thing. Solved it under 20 ms.
Problem 129 is easy to brute force. Some observation is required to make this problem simple and easy. This problem is very closely related to problem 26.
Problem 130 is also very simple. If we do not care to use brute force, the result can be found in 20ms or so. But smq and hk extended the problem to the limit of 2500. The problem becomes extremely time costly. I tried the limit = 1000, needs 10 seconds. limit 2500 needs 79 second. I do not want to waste time to 2500 since it takes more than half an hour.
Problem 132 is quite simple if one reviewed the discussion thread of problem 129 and 130. I generated all primes up to 500K, and it just take 50ms to find the first forty prime factors. In the discussion thread, daniel.is.fischer asks the sum of prime factors below 1e9. I tried it, it is quite difficult, my code runs for near 6 minutes to get the answer. I did not figure out how they made it to 1 minute.
Problem 133 looks like quite different, but still the same thing. Solved it under 20 ms.
Subscribe to:
Posts (Atom)