Problem 214 of Project Euler requires one to find the sum of all the prime numbers upto 40000000 that have a totient chain of length 25.
I solved this problem by brute-force using memoization to prevent solving the same sub-problem over and over again. The values I memoized are:
One final thing to point out is the property of totient function for prime numbers.The totient value of a prime number n is n-1. There’s yet another property that could have further increased the performance – totient(n) * totient(m) = totient(m*n) if gcd(m,n) = 1.
All one needs to do is to compute the totient value of each number from 1 to 40000000. Then starting from n = 1 through n = 4000000, we need to update the value of totient_chain_length as totient_chain_length(n) = totient_chain_length(totient(n)) + 1.
Instead of computing all the values, I instead chose to compute and memoize them as required. Since only the chains starting with prime numbers are required, I got a generator of primes till 40000000. Iterating over the elements of the generator, I updated the totient_chain_length as mentioned above, calculating the missing values whenever required.
Here’s the main script that does this computation:
The general purpose memoize class is:
And the method used for computing the totient values is (note that it can be further optimized):
is_probable_prime actually is the Miller-Rabin test with a default trials value set to 5. However since I had already precomputed all the prime numbers till 40000000 it was a small matter of checking against the generated list.