Question about A018804
Pieter Moree
moree at science.uva.nl
Wed Dec 3 12:05:31 CET 2003
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
More information about the SeqFan
mailing list