Factorisation triples
This is an easy problem. When the problem is posted, I felt that it is not very difficult. It looks like similar to problem 266, but I did not play with it seriously. Today, I still do not have too much clue on it. I tried to answer some fundamental questions like "how to express 43! in terms of prime numbers and how many factors does 43! have". After a while, I see what I need to do. I implemented some simple code and it takes 500 seconds to get the answer! It is slow, however the answer is correct. I optimized my code and tried to start searching in a different place. It only takes 5 seconds to get the answer.
Wednesday, August 28, 2013
Thursday, August 22, 2013
project euler problem 267
Billionaire
A simple problem. The problem is about maximum and probability. Once this is understood, the rest part is very easy. It takes only 1ms.
A simple problem. The problem is about maximum and probability. Once this is understood, the rest part is very easy. It takes only 1ms.
Wednesday, August 14, 2013
project euler problem 268
Counting numbers with at least four distinct prime factors less than 100
A great problem.
I checked my old code. It runs very slow, near 40 seconds. The worst thing is that I do not know how to speed it up. I checked the discussion and found that it is still about principle of inclusion-exclusion, but our job is to remove the over-count. I wrote some new code and it only takes 0.15 second to get the answer.
A great problem.
I checked my old code. It runs very slow, near 40 seconds. The worst thing is that I do not know how to speed it up. I checked the discussion and found that it is still about principle of inclusion-exclusion, but our job is to remove the over-count. I wrote some new code and it only takes 0.15 second to get the answer.
Sunday, August 11, 2013
project euler problem 430
Range flips
This problem looks like very difficult, but actually it is not. It is a very simple probability problem. After some derivation, I got a formula and there is no need to write any code!
The key point in this problem is that "range" is a misleading word.
This problem looks like very difficult, but actually it is not. It is a very simple probability problem. After some derivation, I got a formula and there is no need to write any code!
The key point in this problem is that "range" is a misleading word.
project euler problem 421
Prime factors of n15+1
I am very happy that this problem is solved. Although my solution is not as elegant as those guys who solved it in a couple of hours after the problem was posted. But it is not too bad. It takes 23 seconds to get the answer.
I do not know how to solve this problem after I read the problem. Although I knew how to do the factorization of n15+1(polynomial), but it is useless. The numbers are huge! Then, I found some old problems are closely related to this problem, i.e., problem 271 and 272. I reviewed the discussion of these two problems and found some real gems in the discussion! It really helps to solve the problem!
I really believe reading the discussion of a problem is as important as solving a problem by oneself. In some sense, it is even more important than solving a problem. A lot of genius gave incisive comments in the discussion that we may benefit from.
Friday, August 9, 2013
project euler problem 431
Square Space Silo
The funniest problem of all PE problems. Words like "have three squared decimal places" are really humorous. What a square paranoia Fred is! Well, the PE development team are integer paranoia!
The problem is not very difficult to solve since we only need to find the wasted volume. It is a one dimensional integration problem. One just needs to be careful about the accuracy. There is not too much trick in the problem.
The funniest problem of all PE problems. Words like "have three squared decimal places" are really humorous. What a square paranoia Fred is! Well, the PE development team are integer paranoia!
The problem is not very difficult to solve since we only need to find the wasted volume. It is a one dimensional integration problem. One just needs to be careful about the accuracy. There is not too much trick in the problem.
Wednesday, August 7, 2013
project euler problem 272
Modular Cubes, part 2
This problem is more difficult than problem 271. I lost my old code, so I wrote a new code. I made some mistakes in the code, but soon I fixed those bugs. I checked the clarification of the problem, but some of the guy's result is not correct. I spent a lot of time debugging the case of 3e7, 3e8. But finally I found my code is correct!
My code runs 2 second. One need to memorize some result to speed up the code. That being said, it is still very tricky to count the number of solutions of the same type!
Update: The discussion of this problem is very helpful. I learned a great deal from the discussion. I solved problem 421 with the help of the discussion.
This problem is more difficult than problem 271. I lost my old code, so I wrote a new code. I made some mistakes in the code, but soon I fixed those bugs. I checked the clarification of the problem, but some of the guy's result is not correct. I spent a lot of time debugging the case of 3e7, 3e8. But finally I found my code is correct!
My code runs 2 second. One need to memorize some result to speed up the code. That being said, it is still very tricky to count the number of solutions of the same type!
Update: The discussion of this problem is very helpful. I learned a great deal from the discussion. I solved problem 421 with the help of the discussion.
Sunday, August 4, 2013
project euler problem 271
Modular Cubes, part 1
This problem is simple. But pure brute force is not an option. I checked my old code, I kept a list of "possible solutions" and used something like bigInteger to do the modulo work since the numbers are too big. It only takes 17 ms, not too bad!
This time, I tried to avoid using bigIntegers since most of the problems with a number greater than 150 may be solved without the help of GMP. I found there is a better solution which used the famous Chinese Remainder Theorem. The problem is extremely simple after one understand what is going on inside CRT. Quite a few other project euler problems also check one's understanding of CRT, this one being the simplest one. It is a good opportunity to learn CRT!
My code runs less than 10 ms.
This problem is simple. But pure brute force is not an option. I checked my old code, I kept a list of "possible solutions" and used something like bigInteger to do the modulo work since the numbers are too big. It only takes 17 ms, not too bad!
This time, I tried to avoid using bigIntegers since most of the problems with a number greater than 150 may be solved without the help of GMP. I found there is a better solution which used the famous Chinese Remainder Theorem. The problem is extremely simple after one understand what is going on inside CRT. Quite a few other project euler problems also check one's understanding of CRT, this one being the simplest one. It is a good opportunity to learn CRT!
My code runs less than 10 ms.
project euler problem 417
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!
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!
Saturday, August 3, 2013
project euler problem 412
Gnomon numbering
This problem is relatively easy with the help of google.I did some search about the problem and find wikipedia and mathworld provide some very useful information. I do not want to give too much hint since the search takes little effort. After I understood what needs to be computed, the rest is really simple since 76543217 is a prime.
It takes 0.35 second to get the correct answer.
Thursday, August 1, 2013
project euler problem 374
Maximum Integer Partition Product
This problem is relatively easy to solve.
PE problems are more and more difficult to solve now since the number are huge! 1e14, 1e18 or 1e19 are very popular in problems with a problem number greater than 350. It means if you cannot find some formula, it is almost impossible to solve the problem.
I got some help from google. After that, the problem is very straight forward. But I still got stuck by overflow issue for some time. My code runs for 5 seconds.
This problem is relatively easy to solve.
PE problems are more and more difficult to solve now since the number are huge! 1e14, 1e18 or 1e19 are very popular in problems with a problem number greater than 350. It means if you cannot find some formula, it is almost impossible to solve the problem.
I got some help from google. After that, the problem is very straight forward. But I still got stuck by overflow issue for some time. My code runs for 5 seconds.
Subscribe to:
Posts (Atom)