2
$\begingroup$

For a given $N$, is there an approach to find the maximum $\frac{\phi(i)}i$ ($2\le i\le N$)?

Like for $n=2$, $\frac{\phi(2)}2=\frac12$ is maximum

for $n=3$, $\frac{\phi(3)}3=\frac23$ is maximum

for $n=4$, $\frac{\phi(3)}3=\frac23$ is maximum

From wikipedia's definition : $\frac{\phi(n)}n = \prod_{p|n}\left (1 - \frac1p\right)$.

So, I guess $p$ should be very big for this approach. Still, I can't find a generalised approach. Please help.

$\endgroup$
  • $\begingroup$ What do you mean "maximum": $\,\frac{\phi(3)}{3}=\frac23\,$ , just like that. It's not a maximum but just a value. A maximum can be searched from a set with at least two values, otherwise it is trivial. $\endgroup$ – DonAntonio May 4 '13 at 10:31
  • $\begingroup$ There is a set.The set consists of all phi(i)/i for 2≤i≤n $\endgroup$ – mohan May 4 '13 at 10:32
  • $\begingroup$ Oh, I see...now $\endgroup$ – DonAntonio May 4 '13 at 10:33
  • $\begingroup$ Your guess that $\max\{\frac{\phi(i)}i\mid 2\le i\le n\}$ equals $\frac24=\frac12$ when $n=4$, is wrong. Obviously, $\frac23$ is bigger. $\endgroup$ – Hagen von Eitzen May 4 '13 at 10:37
  • $\begingroup$ Oh ya,edited !! $\endgroup$ – mohan May 4 '13 at 10:39
4
$\begingroup$

Let $n\ge 2$ be given and $p$ the biggest prime $\le p$. Then $\frac{\phi(p)}p=1-\frac1p$. If $2\le i\le n$, then $i$ has $m\ge1$ prime factors $q_k\le p$ ($1\le k\le m$), hence $$\frac{\phi(i)}i=\prod_{k=1}^m\left(1-\frac1{q_k}\right)\le \left(1-\frac1p\right)^m\le 1-\frac1p.$$ Thus $1-\frac1p$ is indeed the maximum value: If $n\ge2$, then $$\max\left\{\frac{\phi(i)}i\biggm| 2\le i\le n\right\} =1-\frac1{\max\{p\mid p\le n, p\text{ prime}\}} $$

$\endgroup$
  • $\begingroup$ So, basically we will get the maximum value everytime for the biggest prime (just less or equal to n)? $\endgroup$ – mohan May 4 '13 at 10:54
1
$\begingroup$

Yes this ratio will be maximum for the largest prime less than equal to N. Now the question is, how would you compute such prime when N is very large.

$\endgroup$

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.