Question about A018804

[Pieter Moree]

Dear list:

>So, I would bet, but not my life, that
>
>limit{n->oo}
>(sum{k=1 to n} GCD(k,n))/(sum{k=1 to n} d(k))
>
>converges to some constant, if not 1.
>>
>>Am I right, or did I make an error above?

You made an error. The first sum depends higly on the factorisation of
n. If n is a prime this sum equals 2p-1. The second sum
behaves as p*logp. So the quotient can certainly get
arbitrarily small.

On the other hand, consider n of the form 2^m. Then the first
sum equals 2^m(1+m/2) and the fraction you consider tends
to a limit for m tending to infinity.

Call the quotient you consider F(n).
I expect that in the setting of the probabilistic theory
of numbers a sensible formulation of your statement could be
given and a result a la the celebrated Erdos-Kac theorem holds
true, so for an `average' number you are in some sense right,
but then with the constant 1 replaced by 6/Pi^2.

I claim that the following is true:

************

limit{n->oo}
\sum_{n\le x}(sum{k=1 to n} GCD(k,n))/\sum_{n\le x}(sum{k=1 to n} d(k))
=6/Pi^2.

*************

Proof (sketch). We have
sum k=1 to n GCD(k,n) = \sum_{m|n}m \sum_{k_1<=n/m, gcd(k_1,n/m)=1}1
=\sum_{m|n}m phi(n/m).

The average of GCD(k,n) over 1<= k<=n thus equals

sum k|n phi(k)/k


-------
Aside:

As a rule of thumb phi(k) when averaged over sufficiently many k
behaves as a constant times k. Thus the idea is that

(sum{k=1 to n} GCD(k,n)) behaves as  n * d(n) * constant

I  guess it might be interesting to have a plot of

sum{k=1 to n} GCD(k,n))/(n*d(n)), especially a histogram

In my own work I encountered \sum_{n\le x}1/phi(n) and
\sum_{n\le x}1/(nphi(n)) and they behave as though \phi(n)
is replaced by n * constant. (The constant need not always
be the same !)
-----------------

Given an arithmetic function f(n) we can consider its generating
series \sum_{n=1}^{\infinity}f(n)/n^s. Knowing the generating
series can be sometimes used to determine \sum_{n\le x}f(n).

It is well-known and easy to derive that the generating series
of \sum phi(n)/(n.n^s) equals \zeta(s)/\zeta(s+1).
(with zeta(s) the Riemann zeta function)

Using this it follows that the generating series of
sum k|n phi(k)/k is \zeta(s)^2/\zeta(s+1).

The generating series of d(n) on the other hand is \zeta(s)^2.

Applying the Wiener-Ikehara theorem it then follows that

sum _{n\le x} sum k|n phi(k)/k behaves asymptotically as x*log
x/\zeta(2) sum_{n\le x} d(n) behaves asymptotically as x*log x.

By partial integration we
then infer that \sum_{n\le x}(sum{k=1 to n} GCD(k,n)) behaves
asymptotically as x^2*log(x)/(2*\zeta(2))

On the otherhand \sum_{n\le x}\sum_{k\le n}d(k)
\sum_{n\le x}(sum{k=1 to n} d(k)) behaves asymptotically
as x^2*log(x)/2.

End of sketch.

With some more work one no doubt can find small order terms.

Bests,
Pieter Moree