Project Euler problem 214, How can i make it more efficient?

Question

I am becoming more and more addicted to the Project Euler problems. However since one week I am stuck with the #214.

Here is a short version of the problem: PHI() is Euler's totient function, i.e. for any given integer n, PHI(n)=numbers of k<=n for which gcd(k,n)=1.

We can iterate PHI() to create a chain. For example starting from 18:

PHI(18)=6 => PHI(6)=2 => PHI(2)=1.

So starting from 18 we get a chain of length 4 (18,6,2,1)

The problem is to calculate the sum of all primes less than 40e6 which generate a chain of length 25.

I built a function that calculates the chain length of any number and I tested it for
small values: it works well and fast.
sum of all primes<=20 which generate a chain of length 4: 12
sum of all primes<=1000 which generate a chain of length 10: 39383

Unfortunately my algorithm doesn't scale well. When I apply it to the problem, it takes several hours to calculate... so I stop it because the Project Euler problems must be solved in less than one minute.

I thought that my prime detection function might be slow so I fed the program with a list of primes <40e6 to avoid the primality test... The code runs now a little bit faster, but there is still no way to get a solution in less than a few hours (and I don't want this).

So is there any "magic trick" that I am missing here ? I really don't understand how to be more efficient on this one...

I am not asking for the solution, because fighting with optimization is all the fun of Project Euler. However, any small hint that could put me on the right track would be welcome.

Thanks !

Answer 1

I've not solved it, but I'm thinking you might be on the right track with your caching scheme, you just might not be caching the right thing. Hope that's not too much or too obscure a "hint" for you.

Answer 2

I'll make a wild guess that the time-consuming part is calculating the totients of the numbers.

One thought could be to try and generate these in some clever way. Think about if it would be possible to calculate them all at once, instead of doing the calculation for one number at a time...

Also, how are you calculating the totient function? The definition (number of integers k where gcd(n,k)==1) is not a useful way to work with it. Look it up and see if you can find a more suitable formula for it.

Edit: Yup, that's the expression I was after. But going through each integer, factoring it, and computing the totient is too slow. Look for a way to compute the totients without doing any factoring...

Answer 3

Well, I'm not familiar with it, and you don't show what you are doing... but some thoughts:

• simplify the gcd; you don't need to know the answer - just whether there is any common factor - so factorise the smaller number (from the list of primes) and test each term against the larger number

Answer 4

One thing to realize is that once you reach to 6 for example, the rest of the chain is always 2,1.

Answer 5

Sorry the formatting of the comment is wrong and I can't delete it. So here it is again:

To calculate the totient function, I use the following: For a given n, let's call p the list of it's factors.
phi(n)=n*prod((p-1)/p)

ex: 2,3 are factors of 18 => phi(18) = 18 * 1/2 * 2/3 = 6

So in this way I don't calculate any gcd. The function that gives me the factors is built in MATLAB (yep, I forgot to mention that I code in Matlab). Maybe I should rewrite the factorization function...

Answer 6

Try going backwards... (start from 1, 2, etc., and work your way up rather than trying to go back down and link into chains)

edit: also note that totient(x) has a particular structure, namely totient(x) = x * the product of (1-(1/p)) where p are the distinct prime factors that divide x.

Answer 7

Hints:

1. Use memoisation and do not calculate phi(n) more than once.

2. Try to use values of phi() that you already calculated for smaller n, when calculating phi(N). Something like phi(m*n) = phi(m) * phi(n) [What property should m and n have for this to hold?]

3. Do you know what is phi(p) when p is a prime?