Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This exercise is meant to be 'explored' computationally. However, I implemented it in C++ and did not get anything better than a sequence of pseudo-random numbers.

Let $\Phi(n)=\sum_{i=1}^{n}\phi(n)$. Investigate the value of $\Phi(n)/n^2$ for increasingly large values of $n$, such as $n=100$, $n=1000$, and $n=10000$. Can you make a conjecture about the limit of this ratio as $n$ grows large without bound?

Notice that $\Phi(n)=n\phi(n)$. Hence, $\Phi(n)/n^2=\phi(n)/n$. Moreover, the largest value $\phi(n)/n$ ever attains is $1$ at $n=1$; everything else falls within the interval $(0,1)$, and the closest it gets to $1$ again is when $n$ is prime (since $\phi(p)=p-1$, and $(p-1)/p\approx1$ for very large primes $p$).

However, I am tempted to say that this function diverges, and that no conjecture about its limit can be concluded as a result.

What do you guys think?

share|improve this question
    
Since $\phi(n)$ is asymptotically $n$, I'm tempted to say $\Phi(n)/n^2$ approaches $1/2$, as $\sum\limits_{i=1}^ni=\frac{i^2+i}{2}$. –  Alex Becker Feb 25 '12 at 3:20
4  
I think the question is supposed to be about $\sum_{i=1}^n\phi(i)$. –  Gerry Myerson Feb 25 '12 at 3:22
    
Gerry, I thought the same. However, I copied the book's question character by character (Elementary Number Theory and Its Applications 5E. by Kenneth H. Rosen, page 237). Could he have made a typo? –  Josué Molina Feb 25 '12 at 3:27
    
I think the function $f(n) = \phi(n)/n$ has no limit, because for any value taken by $f$, say $f(n_0)$, then $(n_0^k)_{k>0}$ defines a subsequence that converges to this value (using the fact that $f(n_0^k) = f(n_0)$). –  Joel Cohen Feb 25 '12 at 3:36
    
Hey guys, look at what I found. en.wikipedia.org/wiki/… Is that corroborating that the limit indeed does not exist? The mathematics are too convoluted for me to understand at this point. :/ –  Josué Molina Feb 25 '12 at 3:46

2 Answers 2

up vote 7 down vote accepted

There is a very old result that says $$\lim_{n\to\infty}\frac{\sum_{k=1}^n \varphi(k)}{n^2}=\frac{3}{\pi^2}.$$

The error term I have in notes is $O(x(\log x)^{2/3}(\log\log x)^{4/3})$, but undoubtedly there have been improvements on that. There is a large literature.

Added: The OP quoted correctly the textbook source of the problem, which asks about the behaviour of $(\sum_{i=1}^n\varphi(n))/n^2$. This is undoubtedly a typo, since $\sum_{i=1}^n\varphi(n)=n\varphi(n)$.

The ratio $\dfrac{\varphi(n)}{n}$ certainly bounces around a lot, and can be made arbitrarily close to $0$, and, much more easily, arbitrarily close to $1$.

share|improve this answer
    
Is that considering $\Phi(n)=\sum_{i=1}^{n}\phi(n)$ or $\Phi(n)=\sum_{i=1}^{n}\phi(i)$? –  Josué Molina Feb 25 '12 at 4:50
    
What you wrote, both in the post and in the comment, cannot be right, since you are writing $\sum_{i=1}^n \varphi(n)$. I assumed that you mean $\sum_{i=1}^n\varphi(i)$. If we are summing over the divisors of $n$, that is an entirely different function, easy to get explicit formulas for, but somewhat chaotic. –  André Nicolas Feb 25 '12 at 4:58
1  
The typo is fixed in the sixth edition, which defines $\Phi(n)$ to be $\sum_{i=1}^n \phi(i)$. –  David Moews Feb 25 '12 at 5:51
    
@AndréNicolas: "Undoubtedly there have been improvements on that." Surprisingly, there haven't been any. That result is due to Walfisz, and it remains the best. See this blog post for details: enaslund.wordpress.com/2012/01/15/… –  Eric Naslund Feb 25 '12 at 13:44

Here is a detailed note regarding the Totient Summatory function. Part 1 and 2 should be of interest, and in part 2 there is a short proof.

Also see this Math Stack Exchange question and answer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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