project euler problem 231

The prime factorisation of binomial coefficients

This problem is very simple. It is actually almost doing the same thing as problem 429 does. I checked my old code. It takes more than 3 seconds to get the answer since I did not manage those factors very well. I revised the code a little bit. Now it only takes less than 0.5 second.

project euler problem 226

A Scoop of Blancmange

This problem is not very difficult. The most critical part is to find the intersection point between the curve and the circle. It looks like extremely difficult. But we just need an approximate answer.  The rest part is just a numerical integral. 

project euler problem 228

Minkowski Sums

This problem is simple once the property of Minkowski Sums is known. I learned it from Wikipedia. The problem is easy to solve. I guess this problem is created in honor of Hermann Minkowski since he was born in 1864 and passed away in January 12, 1909.  Notice the problem is published in January 16, 2009.

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 354

Distances in a bee's honeycomb

This problem is relatively easy for people who have solved 300+ problems, although only 230 people solved it. But one needs to find the "magic formula"  for this problem. It is not that hard to find the formula. Figuring out those examples are close. It takes 13 seconds for my code to get the answer.

project euler problem 229

Four Representations using Squares

This problem is very difficult if one can fully understand the math behind the problem and solve it in a mathematical way. But If we do not mind to solve it in an easier way,  it is kind of straight forward and the code is easy to write. We have used this method to find primes, factors of numbers, etc....

I tried to reduce the memory usage and break the whole range into a lot of small segments. The memory usage is reduced and the problem is solved in much less time! I used 11.8 seconds to get the answer.

Although I still need to understand more about the math behind the problem, I still learned some math about Jacobi symbol! The property of Jacobi symbol is really amazing!

project euler problem 230

Fibonacci Words

This problem is quite simple. It is straight forward to solve although the problem looks like formidable. 

project euler problem 227

The Chase

This problem is a very easy problem. It is about basic probability theory. The solve of the matrix is also very easy. But I do not see why only 1100 people solved it.

project euler problem 224

Almost right-angled triangles II, revisit

This problem is related to problem 221 and 223. If you solve either of them, this one is not that hard. Otherwise, the solution might be very costly.  I tried factorization method. Although I have used some of the result from previous problem, it is still very slow. It takes 20 seconds. I will try Doraki's algorithm tomorrow. 

project euler problem 223

Almost right-angled triangles I, Revisit

This problem is very difficult.  One algorithm is easy to come up with. But it is not very efficient. It is quite slow. My code runs for 20 seconds. Doraki provided a very nice algorithm in the first page.  It only takes a few seconds using Doraki's algorithm. I am very eager to know if there is any efficient method to solve it in one second.

project euler problem 225

Tribonacci non-divisors

This problem is not difficult since we are only required to find the 124th odd number. But the maths behind it is quite interesting. 

project euler problem 222

sphere packing


I learned quite a bit from this problem. 

First, this problem can be solved by pencil and paper. I learned it from BrianHuffman on the third page of the discussion thread. BrianHuffman's explanation is very lucid. I like it.

 I also practiced Dynamic programming method and random number method on this problem. Dynamic programming method gives me definite result but it takes a little bit more time(5-6 seconds). I also tried with some random number method, it seems inefficient but the result is just the opposite. It only takes 8ms. 

project euler problem 221

Alexandrian Integers

My old code is close to brute force. It runs for 4.4 seconds after I restricted the number to be tested. 

I used the algorithm that is used in problem 216. It is quite fast. Only 0.3 second needed. There is a few other algorithms that is also very fast to solve this problem.

project euler problem 217

Balanced Numbers 

This is an interesting problem. My old code use very cumbersome sum and counting algorithms. But since we just need a number modulo 3^15, we can do it more efficiently.  I do not understand why we are asked to give T(47), T(10000) is more challenging. I wrote poor quality code for T(47). But after I tried to solve T(10000), the algorithm need to be carefully thought over.

My algorithm can compute T(10000) in about 5 seconds.  After I checked some of the code in the discussion. I can speed up my code by a factor of 2.x . I played with the code for two days for better performance.

project euler problem 218

Perfect right-angled triangles

The strangest problem of all PE problems. You will see what I mean when you solved the 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 215

Crack-free Walls

This is a  relatively easy problem. My code's run time is 20 ms. I did not get too much from the discussion.

project euler prolem 214

Totient Chains

This problem is not very interesting. It is pretty straight forward. I did not find a super fast solution in the discussion.  My code's runtime is 2.2 second. 

project euler problem 213

Flea Circus

This is a simple probability problem.  I lost my old code. But based on the discussion thread, I guess I used a Markov-Chain approach. This time,  it puzzled me for half an hour.  I suddenly figured out that this is similar to the "birthday problem", then it is solved. It only takes 200 ms for my new code. I then considered the symmetric property, the run time is reduce to 50 ms.

project euler problem 212

Combined Volume of Cuboids

This is an interesting problem. My old code used an inefficient algorithm(although the basic idea is in the right direction). It takes minutes to get the answer. 

The discussion is very interesting. Robert_Gerbicz gave a very efficient algorithm that I missed. I wrote my code using the same idea, it only needs 80 ms while a lot of people needs 10 seconds to minutes to get the answer. Thank you Robert,  for giving me a different view of the problem. 

project euler problem 211

Divisor Square Sum

I used two method to solve this problem. One is simple and straight forward. But the performance is poor, about 20 seconds.  The second one is using recursion. It takes 2.4 seconds to get the answer. 

I am surprised to see quite a few people using very slow brute force method in the discussion. It takes several hours or even days to get the answer. Why not think it over and let computer have a break?

project euler problem 210

Obtuse Angled Triangles

This problem is not very interesting. It is not difficult at all. A brute force solution is easy to be coded in 5 minutes. But one potential issue about accuracy may exist. I learned one trick from the discussion that removed the sqrt computation from most of my code. My original code runs for 1.2 second and my new code only needs 0.17 second. 

The background of this problem is very famous. Those guys in discussion are quite knowledgeable. It seems that they knew everything about math and coding. 

project euler problem 209

Circular Logic

This problem is relatively simple.  The keyword is circular.  We just need  to find how many elements are in the same circle. Then we just need to find the number of different configurations that satisfy the condition. It is a simple dynamic programming problem. 

project euler problem 208

Robot Walks

This problem is very interesting, and also very difficult. I like it. When I first tried to solve it, I have no clue.  It take me several days to find out what I am supposed to do. I even used the pentaflake figure from mathworld to test some of my idea. Finally, I found the problem was simpler than I thought. The clarification of problem 208 is very useful. One may get a lot of hint from the discussion. 

I first used quite complicated struct to solve this problem. It takes more than five seconds. After I simplified the struct to two integers, it is solved in less than 3 second. 

Today,  I reviewed the discussion. I found that I can use some symmetry properties to reduce the search space. Then it takes only less than 0.5 second to solve the problem. 

project euler problem 207

Integer partition equations

I do not understand why only less than 2700 people solved this problem. The problem is as simple as problem 206 and 205. 

project euler problem 206

Concealed Square

The simplest problem after problem 200! If one thought it over, the problem can be solved faster. 

project euler problem 205

Dice Game

This is a very simple problem. I am surprised why more than 7500 people solved it.  For problem with an ID greater than 200, usually only less than 1000 people can solve it.

project euler problem 204

Generalized Hamming Numbers

This is a very simple problem. I used recursion. It only takes 40 ms. 

project euler problem 203

Square-free Binomial Coefficients

This problem is too simple. The number of lines is too small, there are only limited numbers to be checked. I was using factorization in my old code, but I found that it was not necessary at all.

There are one or two more challenging PE problem closely related to this problem.   

project euler problem 202

Laser beam

This looks more like a physics problem, but involved some math and coding. Once you understand what you should do, it is very simple.  It takes less than 1 ms.

project euler problem 201

Subsets with a unique sum

The problem is not so interesting. I did not learn too much from the problem. Since there are so many combinations, even if my code has some logic bugs, I still get the correct answer. The ways to solve this problem are almost near brute force. 

project euler problem 200

Find the 200th prime-proof sqube containing the contiguous sub-string "200"

Not a very interesting problem. I do not like it very much. almost everyone is doing the same thing.  

project euler problem 199

Iterative Circle Packing

This is a math problem. Not too much coding needed. If one can solve the geometry problem by himself, one may have a wonderful day. 

project euler problem 198

Ambiguous Numbers

This is probably the most confusing problem in all PE problems. So many people are confused by the definition of amibuous number and cannot get the correct answer. The following sentence need to be carefully read and interpreted. 

"We shall call a real number x ambiguous, if there is at least one denominator bound for which x possesses two best approximations."

A lot of hint and helpful message are given here. After we understand what "trivial" means, the rest are not so difficult. 

Actually, there is some related problems to this one. The problem number is between 50 to 80. If the simpler problem can be solved efficiently, this one can be done similarly. My code finished in 0.2 second.

project euler problem 197

Investigating the behaviour of a recursively defined sequence

The problem is very easy. But it is not easy to explain the math behind it.

project euler problem 196

Prime triplets

This problem is relatively simple. One just needs to find all primes in range [low, high]. The problem is well defined and easy to solve. My code is not so nice. But it runs under 1 second. 

project euler problem 195

Inscribed circles of triangles with one angle of 60 degrees

I like this problem. When I first tried to solve this problem. I found some quick formula for the problem and solved the problem in 1 second. This time, I revised the code a little bit, checking gcd as the last criteria, my code's run time reduced to 0.47 second.

After I read the discussion thread, I recommend everyone read lomont's post on the second page. It is a brief but interesting tutorial about Eisenstein integers.