project euler problem 160

Factorial trailing digits

I like this problem. At first glance, it seems impossible to solve the problem since there are too many trailing zeroes for factorial(10^12). Then I took a look at my old code. I managed to get rid of all those 2 and 5 in the code. It works pretty good. Only  4 ms needed to solve this problem.

project euler problem 154

Exploring Pascal's pyramid

I lost my old code. What is embarrassing is that I do not know how to solve it after I read the problem. After sometime's thought, I decided to use brute force method(This proved to be the only way to solve it). After considering some symmetry property of this problem, I managed to reduce the run time to 6 seconds.

I checked some of the guy's code in c or c++, I found they can make it at 3 to 4 seconds!   I compared the code for quite some time. Finally, I found that the order of checking criteria was very important since we run them for so many times! Just like if several conditions need to be checked, if we need to check gcd, it should always be the last one. Finally I can get the result in 3.5 seconds.

project euler problem 383

Divisibility comparison between factorials

This problem is not quite interesting. But from this problem, I realize that learning something is more important than just solving some problems! 

I have been reviewing all my solved problems recently, and after I learned something from an old problem, I realized that I should give this problem a shot.

Since the problem asks n < 10^18, we can not check each number. The first thing is to find an equivalent problem that can be relatively easy solved. If you say you cannot find it, I would recommend you to review all problem between 140 and 150 and read TAOCP volume 1, 1.2.6 exercise. 

The second thing is to solve this relatively easy problem. I should admit that the logic is still not so straight forward to be translated into code. I spent quite some time debugging n=100 and n=1000 until I found that I have some logic error. After that, the problem is solved with in 1 ms!

project euler problem 148

Exploring Pascal's triangle

This is an interesting problem. I like this problem. 

I do not know how I solved this problem the first time because I cannot find my old code. I really want to know what I thought at that time. I guess it should be similar to what lzw75 did in the discussion thread. 

This time, I read Knuth's book(TAOCP, vol 1). I got a better understanding of this problem. I also read hyperdex's explanation of the problem. It is really interesting! 

project euler problem 074

Digit factorial chains

This problem is interesting. It is not difficult to brute force. But finding a very efficient algorithm is not that easy.  My code runs 0.7second without too much memory cost. The key is to avoid duplicate computation.

PE problem makers like factorial quite a bit. There are quite a few more difficult problems that are related with factorials.

update 09/25/2017:
the old code is still hard to read. I rewrote the recursive function to find the different numbers in the list. The logic is easier to understand now.

project euler problem 034

Digit factorials

  A little bit thought about the upper bound is required. Then  the problem can be
solved in 0.1s. Although this problem is easy, later on, the PE problems about factorial are not so easy to solve.