Optimum polynomial
This problem is not difficult. I used matrix solve to find the optimal polynomial. After I read the discussion thread, I found there was a better solution for this problem, which can make everything simpler. I never heard of the algorithm before. Please take a look at the thread to learn it.
Tuesday, April 9, 2013
Monday, April 8, 2013
project euler problem 100
Arranged probability
This problem is simple if problem 66 has been solved. These two problems are closely related. Actually this problem is easier than problem 66. Brute force is not an option. It takes less than 1ms to get the answer.
This problem is simple if problem 66 has been solved. These two problems are closely related. Actually this problem is easier than problem 66. Brute force is not an option. It takes less than 1ms to get the answer.
project euler problem 099
Largest exponential
This is a very simple problem. It can not be simpler. Everyone can solve it. At least for those who like math.
This is a very simple problem. It can not be simpler. Everyone can solve it. At least for those who like math.
project euler problem 097
Large non-Mersenne prime
This problem is easy if one has an efficient algorithm to calculate power. Another headache is to find value mod 10^10 correctly. If either is not an issue, the problem is extremely simple. It takes less than 1ms.
This problem is easy if one has an efficient algorithm to calculate power. Another headache is to find value mod 10^10 correctly. If either is not an issue, the problem is extremely simple. It takes less than 1ms.
project euler problem 095
Amicable chains
I checked my old code. It was cumbersome. I used set and my algorithm to find all divisors was too slow. It takes 6.5 second to find the answer.
This time, I changed the divisor sum algorithm by using some sieve method. But it is still not very fast since I used hashset to check if the number appeared in the sequence. It is kind of overkill. But this reduced the run time to 0.764 second.
I read the discussion thread and find a better algorithm to stop the sequence. I reimplemented the code, it reduced to 0.196 second with my debug version. Sweet!
I checked my old code. It was cumbersome. I used set and my algorithm to find all divisors was too slow. It takes 6.5 second to find the answer.
This time, I changed the divisor sum algorithm by using some sieve method. But it is still not very fast since I used hashset to check if the number appeared in the sequence. It is kind of overkill. But this reduced the run time to 0.764 second.
I read the discussion thread and find a better algorithm to stop the sequence. I reimplemented the code, it reduced to 0.196 second with my debug version. Sweet!
Sunday, April 7, 2013
project euler problem 094
Almost equilateral triangles
This problem is a little bit challenging. I take a look at my old code, it runs very fast. But I can not figure what I was doing since I did not write any comment. Then I spent an hour to analyze this problem and figured out why I wrote those magic code. It takes 4ms to get the answer.
Pythagorean triplet is critical for an efficient algorithm.
update 10/15/2017
The old code still not works very efficient especially when perimeter goes to 1e18. Actually, after the restriction equation on the sides is determined, it is easy to see that this problem is a Pell Equation problem. Pell equation has very rare solutions and it takes zero ms to figure out all triangles.
This problem is a little bit challenging. I take a look at my old code, it runs very fast. But I can not figure what I was doing since I did not write any comment. Then I spent an hour to analyze this problem and figured out why I wrote those magic code. It takes 4ms to get the answer.
Pythagorean triplet is critical for an efficient algorithm.
update 10/15/2017
The old code still not works very efficient especially when perimeter goes to 1e18. Actually, after the restriction equation on the sides is determined, it is easy to see that this problem is a Pell Equation problem. Pell equation has very rare solutions and it takes zero ms to figure out all triangles.
project euler problem 093
Arithmetic expressions
My old code is too complicated, so I rewrote the code. The new code is much simpler and easier to read. It took 1.7 second for my old code to finish while the new one only needs 0.048 second.
But I do not have a good solution if we change the number of distinct numbers to 10 or even larger number. There is another similar problem in project Euler which is more difficult. Problem 259. Some of the strategy used in this problem may also apply to that problem.
Update 10/13/2017
One version of my code missed the role of parenthesis but the result of the original ProjectEuler problem is still correct. Thanks for projectEuler+ to help me fix the bug.
My old code is too complicated, so I rewrote the code. The new code is much simpler and easier to read. It took 1.7 second for my old code to finish while the new one only needs 0.048 second.
But I do not have a good solution if we change the number of distinct numbers to 10 or even larger number. There is another similar problem in project Euler which is more difficult. Problem 259. Some of the strategy used in this problem may also apply to that problem.
Update 10/13/2017
One version of my code missed the role of parenthesis but the result of the original ProjectEuler problem is still correct. Thanks for projectEuler+ to help me fix the bug.
Subscribe to:
Posts (Atom)