See this image (https://en.m.wikipedia.org/wiki/Euler%27s_totient_function#/media/File%3AEulerPhi.svg) from wikipedia. I can make out two lines that have a high density of values along them. The top line consists of the values of the function at the prime numbers, and then the line below it which has about half its slope I'm not sure about. There's also a third less dense line that is about halfway between them. Can anyone tell me why these other two lines have a comparatively high density of values along them? Also, is the maximum of the totient function for values in [1, n] always achieved at a prime? What is a good asymptotic lower bound for the totient function?

Edit: the answers to my second and third question are in the article containing the image. Can anyone explain the lower bound n/loglogn? I know loglogn is the expected number of prime divisors of a randomly chosen element in [1,n].

  • 1
    $\begingroup$ If $p$ is a prime number, then $\varphi(2p) = p-1$. This may account for one of the high-density lines. The implication though is that the density gets sparser as $n$ goes to infinity. $\endgroup$ – steven gregory Mar 1 '16 at 4:20
  • $\begingroup$ Yes, I mentioned that in my original post. I'm wondering about the other lines. $\endgroup$ – Vik78 Mar 1 '16 at 17:36

As Steven Gregory says, the second line is numbers where $\varphi(n)$ is very close to $n/2$, and this is made up of numbers of the form $2^ap$ where $p$ is prime and $a\geq 1$. The third line is numbers where $\varphi\approx 2n/3$, made up of numbers of the form $3^ap$ where $a\geq1$. There is a rough fourth line of slope $1/3$, which includes numbers of the form $2^a3^bp$, and a fainter one of slope $4/5$ corresponding to $5^ap$. Obviously as the numbers you have to multiply the primes by to reach a particular line get larger, points on that line get sparser.

| cite | improve this answer | |

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.