project euler problem 429

Sum of squares of unitary divisors

Easiest problem in 2013.  I take a look at the problem and find out it is extremely easy. No wonder 470+ people have already solved it.  I wrote the code in 15 minutes and it is solved!  I should admit that I used a few of my functions wrote for other problems. Without those functions, I will need a little bit more time. 

Try it, it is easy. Everyone feels happy to solve this problem!

project euler problem 216

Investigating the primality of numbers of the form 2n^2-1
It is not so easy to find an efficient algorithm.  I checked the discussion, a lot of people' code runs for several minutes to several hours. (If my code cannot finish in 15 minutes, I will definitely kill it).  But still more than 2100 people solved it. It is really strange.

I checked my old code, it looks like that I googled out something from the Internet to solve this problem. Otherwise I have no idea how to solve it.  

This time, I am equipped with a weapon that is related to quadratic residue. My first implementation needs 8 second. Then I checked the discussion, I found stubbscroll has a better solution. I used some of his idea, the run time is reduced to 5 seconds. I also run his code, it only takes 4 seconds. That is probably due to my powmod function.

project euler problem 187

Semiprimes

This is a  really simple problem. It just shows the power of sieves one more time. No wonder more than 5500 people solved it.

project euler problem 146

Investigating a Prime Pattern

This problem is quite difficult.  I do not understand why this one is solved by more than 2000 people but problem 143 is solved only by 1100 people.

I do not have a very straight forward way to solve it. I combined two method into the code. It does not run very fast. 18 seconds. 

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. 

project euler problem 118

Pandigital prime sets

This problem seem not so easy to find an algorithm under 0.1 second. I checked the discussion thread, found that most solutions are at least a couple of seconds (that was posted several years ago) or use a prebuilt prime table. 

It takes 0.6 second for my code to get the answer.

project euler problem 060

Prime pair sets

This might be a relatively difficult problem so far. I checked my old code. It is ugly. I created  prime numbers up to 1e8, which is a huge cost(run time 22s).  I used strong pseduoprime test instead of checking from the prime list, the code run time reduced to 1.4s. But the code structure still looks unacceptable.

 I rewrote my code, following the clever idea found in the discussion thread. The new code looks simpler, but not too much performance gain.

project euler problem 058

Spiral primes

This problem is about the primality of a number. I used two different method to solve this problem. First, use a prime table and second use strong pseudo prime test. The first method takes 0.1 second and the second takes 0.04 second. 

update 09/17/2017. This problem is great, but the 10% requirement is too easy for everyone to get a correct answer, if this number is reduced to 8%, the problem is a lot more difficult since overflow is a challenging issue for primality test. I found a different approach from Inamori and francky's post, which is brilliant. 

project euler problem 051

Prime digit replacements

I like this problem. I looked at my old code, it is ugly and difficult to understand. But after I got the correct answer, I left for the next problem without a better solution.  This time, I read the discussion thread, then I found that I missed a very important fact about "8".  Now I have a better understanding of this problem. 

Good problem!

project euler problem 050

Consecutive prime sum

This problem is simple. Some of the people even assumes that 2 is the first number, still get the correct answer. 

project euler problem 049

Prime permutations

This problem is simple, but my old code is ugly.  But it only take 1.6ms. So I kindly forgave myself. Not too much can be learned from this problem. 

Update(06/28/2017): 
Actually, my old code was inefficient since I used the stl function next_permutation to generate all arithmetic progression sequence. I can combine all the prime numbers that are made from the same group of digits into a vector and check if any arithmetic progression sequence can be created from them, which is more efficient.

project euler problem 037

Truncatable primes

I am a little bit upset I used emacs to figure out how to "continuously remove digits from left to right". Maybe I was watching TV while coding. It is an easy
problem, but I was wondering how to prove that there is only 11 such numbers.

Discussion thread!!!

Zef enlightened me why there are only 11 such numbers, and I learned another way of expressing decimal numbers. It is really interesting! Please read it if you have no idea what I am talking about.

To help others to focus on the discussion thread is one of my goals to write the blog.

project euler problem 035

circular primes

This is a simple problem,  it takes 0.014 second to find the answer. Not too bad. 

My first version was lost. I did not remember how I solved it.   I am happy that I did not split the number into digits in my second version. I see the same strategy on page 2 in the discussion thread.

project euler problem 010, very interesting problem

If you can solve problem 7, there is no difficulty to solve this one.  This can be a very simple problem using the sieve method.

But if you are really interested to count the primes or count the sum of primes under N, the sieve method is not efficient at all when N is large. In the discussion of this problem, a dynamic programming approach is suggested and it is a fast method to count prime numbers. Please do not miss the opportunity to learn if you do not know this method! The code is written in python,  and lucy did an excellent job in his post!

project euler problem 007

This is a warm-up problem.  Very basic.  Read the discussion thread if your code took more than 0.2 second.

project euler problem 005

smallest multiple

calculator problem, every one can solve it.

project euler problem 003

largest prime factor

I use C or C++ to solve project euler problems. But I rarely use long long in coding. After I solved 50 to 100 problems, I found long long is necessity. The problem is easy, even one use some kind of  brute force method. One may read the book from CLRS and try some fancy method. 

It is interesting to notice that for most of the project euler problems that require an integer as an answer, number is usually less than 2^64.