project euler problem 421

Prime factors of n¹⁵+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 n¹⁵+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. 

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.

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. 

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.

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!

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.

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.