Databases
StackOverflow2013
Postsdbo
POProject Euler 214, How can I make it more efficient?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POProject Euler 214, How can I make it more efficient?
    text
    copied!<p>I am becoming more and more addicted to the Project Euler problems. However since one week I am stuck with the <a href="http://projecteuler.net/index.php?section=problems&amp;id=214" rel="nofollow noreferrer">#214</a>.</p> <p>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&lt;=n for which gcd(k,n)=1.</p> <p>We can iterate PHI() to create a chain. For example starting from 18: </p> <blockquote> <p>PHI(18)=6 => PHI(6)=2 => PHI(2)=1.</p> </blockquote> <p>So starting from 18 we get a chain of length 4 (18,6,2,1)</p> <p>The problem is to calculate the sum of all primes less than 40e6 which generate a chain of length 25.</p> <p>I built a function that calculates the chain length of any number and I tested it for <br>small values: it works well and fast.<br> sum of all primes&lt;=20 which generate a chain of length 4: 12 <br> sum of all primes&lt;=1000 which generate a chain of length 10: 39383<br></p> <p>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.</p> <p>I thought that my prime detection function might be slow so I fed the program with a list of primes &lt;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).</p> <p>So is there any "magic trick" that I am missing here ? I really don't understand how to be more efficient on this one...</p> <p>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. </p> <p>Thanks !</p> <hr> <p>Sorry the formatting of the comment is wrong and I can't delete it. So here it is again:</p> <p>To calculate the totient function, I use the following: For a given n, let's call p the list of it's factors.<br> phi(n)=n*prod((p-1)/p) </p> <p>ex: 2,3 are factors of 18 => phi(18) = 18 * 1/2 * 2/3 = 6 </p> <p>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... </p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload