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:

- totient_chain_length(n)
- totient(n)
- primefactors(n)

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:

```
'''
Created on Sep 28, 2012
@author: anuvrat
'''
from utils.prime_utils import totient, primesfrom2to
from utils.memoize import Memoize
@Memoize
def totient_chain_length( n ):
if n in range( 21 ): return ( 1, 1, 2, 3, 3, 4, 3, 4, 4, 4, 4, 5, 4, 5, 4, 5, 5, 6, 4, 5, 5 )[n]
return 1 + totient_chain_length( totient( n ) )
total = 0
for prime in primesfrom2to( 40000000 ):
if prime < 9000000: continue
if totient_chain_length( prime - 1 ) == 24: total += prime
print( total )
```

The general purpose memoize class is:

```
'''
Created on Sep 28, 2012
@author: anuvrat
'''
class Memoize( object ):
'''
classdocs
'''
def __init__( self, f ):
self.f = f
self.cache = {}
def __call__( self, *args ):
if not args in self.cache: self.cache[args] = self.f( *args )
return self.cache[args]
```

And the method used for computing the totient values is (note that it can be further optimized):

```
@Memoize
def totient( n ):
if n == 0: return 1
if is_probable_prime( n ): return n - 1
tot = 1
for p, exp in Counter( primefactors( n ) ).items():
tot *= ( p - 1 ) * p ** ( exp - 1 )
return tot
```

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.