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:
Also I precomputed all the primes till 40000000 so that I do not have to waste time doing that while computing. All the primes were stored in memory. The effect of such high memoization and prime number storage was that my process used almost 1.25 gb of memory.
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.