Numbers for which Euler’s totient function equals 13!
This problem looks like very difficult since 13! is a very large number. But after some analysis, it is still manageable. My old code runs for 0.4 second. But the code looks ugly and lengthy. I rewrote the code and it is 40 lines less and only takes 100ms now.
Showing posts with label totient function. Show all posts
Showing posts with label totient function. Show all posts
Saturday, July 6, 2013
Wednesday, July 3, 2013
project euler problem 243
Resilience
This problem is a very easy problem. Nearly 4000 Eulerians have solved it. There is a small trick before one get the correct answer.
This problem is a very easy problem. Nearly 4000 Eulerians have solved it. There is a small trick before one get the correct answer.
Wednesday, May 22, 2013
project euler problem 188
The hyperexponentiation of a number
Sigh! Another lesson of not learning from the discussion thread.
This problem needs a little bit background knowledge. It is called Euler's theorem. I think it is fair to reveal such kind of information. Otherwise, how can one solve this problem?
I do not even know there is a problem like this. After I solved this problem, I totally forgot it. I lost my old code. I do not even know how I solved it. Now I am trying to solve it again. I immediately realized how to solve it since I had experienced a hard time to solve problem 282: the Ackermann function. If I learned from problem 188, 282 is trivial.
Why 3390 people solved this problem but only 560 people solved problem 282? So many people left from project euler?
Sigh! Another lesson of not learning from the discussion thread.
This problem needs a little bit background knowledge. It is called Euler's theorem. I think it is fair to reveal such kind of information. Otherwise, how can one solve this problem?
I do not even know there is a problem like this. After I solved this problem, I totally forgot it. I lost my old code. I do not even know how I solved it. Now I am trying to solve it again. I immediately realized how to solve it since I had experienced a hard time to solve problem 282: the Ackermann function. If I learned from problem 188, 282 is trivial.
Why 3390 people solved this problem but only 560 people solved problem 282? So many people left from project euler?
Thursday, March 28, 2013
project euler problem 072
Counting fractions
I checked my old code. I was trying to factor each number n, then find the number of relative prime numbers to n. This time I directly calculate the totient function for each number, using sieve.
It takes 3.6s to finish for the old code, while 0.076s for the new code.
I checked my old code. I was trying to factor each number n, then find the number of relative prime numbers to n. This time I directly calculate the totient function for each number, using sieve.
It takes 3.6s to finish for the old code, while 0.076s for the new code.
Wednesday, March 27, 2013
project euler problem 070
Totient permutation
This problem is also about totient function, but it is not so straight forward to find an efficient solution.
I do not have my old code, so I first factored all number and calculate phi(n). It is obvious that this is not a good choice. It takes 8 second to get the answer(debug version). I am not satisfied with this solution. So I used a sieve method to compute all number's totient function. This is better, it takes 5 second in debug version and 1 second in optimized version to get the answer.
This problem is also about totient function, but it is not so straight forward to find an efficient solution.
I do not have my old code, so I first factored all number and calculate phi(n). It is obvious that this is not a good choice. It takes 8 second to get the answer(debug version). I am not satisfied with this solution. So I used a sieve method to compute all number's totient function. This is better, it takes 5 second in debug version and 1 second in optimized version to get the answer.
project euler problem 069
Totient maximum
This is the first problem about Euler's famous totient function or phi function. A lot of PE problems need to use totient function. This one is very straight forward if one understand the basic properties of totient function. It can be solved with the help of a calculator actually.
This is the first problem about Euler's famous totient function or phi function. A lot of PE problems need to use totient function. This one is very straight forward if one understand the basic properties of totient function. It can be solved with the help of a calculator actually.
Subscribe to:
Posts (Atom)