Coin sums
I like this problem. Although it is simple, I still learned a lot from this problem.
There are several ways to solve this problem: Generating function; dynamic programming, recursion. Recursion is the most natural way to solve this problem.
Update (06/17/2017):
The problem may look simple, actually the dynamic programming way is the only simple choice for large N. The recursive way only works for small N. For large N, it is extremely slow. The code in the overview of this problem worth the time to read, especially the one by wizeman.
Friday, March 8, 2013
project euler problem 030
Digit fifth powers
Another simple problem. One may need a moment's thought to give a reasonable upper bound for this problem.
Although the problem can be bruteforced out easily, from a programmer's point of view, an efficient algorithm is preferred. An efficient approach exists for this problem, the numbers checked in the efficient approach is very limited. For example, check only less than 4000 numbers for power = 5 and less than 10000 numbers for power = 6.
The trick is that we can always try large digit first.
Another simple problem. One may need a moment's thought to give a reasonable upper bound for this problem.
Although the problem can be bruteforced out easily, from a programmer's point of view, an efficient algorithm is preferred. An efficient approach exists for this problem, the numbers checked in the efficient approach is very limited. For example, check only less than 4000 numbers for power = 5 and less than 10000 numbers for power = 6.
The trick is that we can always try large digit first.
project euler problem 029, very interesting problem!
Distinct powers
This is a boring problem. It is not a hard problem. One may even solve it by hand.
Update.
I am wrong on this problem, and when I was reviewing this problem several years ago, I am still not very careful about learning from others. This was changed only a few days ago when I was considering the number 100 to be changed to 100000 or larger.
I found my method ate a lot of memory and slow. Then I read the discussion thread again. Wow, the idea by jorgbrown and WP really helps a lot for me to understand the sieve method better! Please try to change the number 100 to 1000000 and see you code can give you the answer in one second or not.
The discussion really changed my view on sieve method, interesting!
This is a boring problem. It is not a hard problem. One may even solve it by hand.
Update.
I am wrong on this problem, and when I was reviewing this problem several years ago, I am still not very careful about learning from others. This was changed only a few days ago when I was considering the number 100 to be changed to 100000 or larger.
I found my method ate a lot of memory and slow. Then I read the discussion thread again. Wow, the idea by jorgbrown and WP really helps a lot for me to understand the sieve method better! Please try to change the number 100 to 1000000 and see you code can give you the answer in one second or not.
The discussion really changed my view on sieve method, interesting!
project euler problem 028
Number spiral diagonals
The 5x5 graph reveals some important fact. Actually this is a O(1) mathematical problem. No more to say about this problem.
The 5x5 graph reveals some important fact. Actually this is a O(1) mathematical problem. No more to say about this problem.
project euler problem 027
Quadratic primes
A simple problem. The only thing I noticed is the formula given by Euler in 1722. With the help of computers, we can do much better than this great mathematician!
But when I read the discussion thread, I was ashamed by such kind of feeling. Euler's formula gave 40 distinct primes. The formula we found gave 71 primes, but only 40 of them are distinct! Our formula is worse in this respect!
The post by hk is also very interesting! He solved the problem without computer! Really amazing!
A simple problem. The only thing I noticed is the formula given by Euler in 1722. With the help of computers, we can do much better than this great mathematician!
But when I read the discussion thread, I was ashamed by such kind of feeling. Euler's formula gave 40 distinct primes. The formula we found gave 71 primes, but only 40 of them are distinct! Our formula is worse in this respect!
The post by hk is also very interesting! He solved the problem without computer! Really amazing!
Wednesday, March 6, 2013
project euler problem 026
reciprocal cycles
An easy problem. Just need to figure out a way to find that the period of recurring cycle. It is really simple. Well, similar idea appears in more difficult
problems such as continued fraction, which is a little bit more difficult to solve.
There is still something that I learned in the discussion thread.
An easy problem. Just need to figure out a way to find that the period of recurring cycle. It is really simple. Well, similar idea appears in more difficult
problems such as continued fraction, which is a little bit more difficult to solve.
There is still something that I learned in the discussion thread.
project euler problem 298
Selective Amnesia
This is not an easy problem. I gave up on this problem for a couple of times. Finally, I made all my effort to simplify this problem, it is solved!
The first part is to transform the pairs of numbers into states, which is quite complicated. I spent half a day or even longer on this part. After this part is done, the task left is just to solve a very easy probability problem. Quite a few problems in Project Euler require such sort of abstraction. For example, problem 324, building a tower.
It takes my code 0.17s to find the answer. It looks like there is still some potential to speed up.
After this problem is solved. I entered level 14. Still another 25 problems left to enter level 15.
This is not an easy problem. I gave up on this problem for a couple of times. Finally, I made all my effort to simplify this problem, it is solved!
The first part is to transform the pairs of numbers into states, which is quite complicated. I spent half a day or even longer on this part. After this part is done, the task left is just to solve a very easy probability problem. Quite a few problems in Project Euler require such sort of abstraction. For example, problem 324, building a tower.
It takes my code 0.17s to find the answer. It looks like there is still some potential to speed up.
After this problem is solved. I entered level 14. Still another 25 problems left to enter level 15.
Subscribe to:
Posts (Atom)