0
$\begingroup$

I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$.

I tried this approach , but is too slow. Finding the just smallest prime number to $N$, as its $\frac{\phi(i)}{i}$ value is $\frac{i-1}{i}$, which is maximum in the range. (See Maximum of ϕ(i)i\frac{\phi(i)}i)

So, I was wondering if there is any other faster way to find the maximum value. More precisely I need the value of i where $\frac{\phi(i)}{i}$ is maximum.

$\endgroup$
2
$\begingroup$

Since you know that the maxium value is achieved when $i$ is the largest prime smaller than $N$, your problem is equivalent to finding the largest prime smaller than $N$.

There are many ways to test for primality, so presumably you could just take your favorite primality test and run a for loop from $N-1$ downwards, to find the first number which is prime.

Perhaps I do not understand what you are asking for.

$\endgroup$
  • $\begingroup$ I tried this approach using Miller-Rabin but it takes 1 minute on my system for 10^18. So, I was looking for any other faster way of finding. $\endgroup$ – user7711 May 8 '13 at 9:57
  • 1
    $\begingroup$ Use sieving first to dramatically improve your running time. $\endgroup$ – Yuval Filmus May 8 '13 at 13:22
  • $\begingroup$ @YuvalFilmus, seiving algorithm is dramatically slower than Miller-Rabin in this case, because he just need one number, also his test was wrong, I suggest a very fast prime algorithm for him, but he added very bad implementation to the algorithm. cs.stackexchange.com/questions/11883/… $\endgroup$ – user742 May 8 '13 at 13:26
  • $\begingroup$ Surely it still makes sense to skip over all even numbers? There is a tradeoff here. While the primality testing algorithm is fast, you'll have to test around $\log N$ integers until you actually find a prime. $\endgroup$ – Yuval Filmus May 8 '13 at 13:34
  • $\begingroup$ @YuvalFilmus, anyway I updated my answer there, but for other readers, when you know the bound you can skip the pseudoprime numbers for specific range, and for this range there are just 8 forbidden number to take care of them, so is constant number of iteration after Miller-Rabin. $\endgroup$ – user742 May 8 '13 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.