Question about A018804

[Leroy Quet]

[some snipped]
>...
>Matthew wrote:
>....
>>>Does anyone know, and if so could someone please tell me, whether the 
>>>"typical" nth term of sequence A018804, the sum of gcd (k,n) for 1 <= k <= 
>>>n  
>>>(a (1) through a (10) are 1, 3, 5, 8, 9, 15, 13, 20, 21, 27 . . . ; see 
>>>http://www.research.att.com/projects/OEIS?Anum=A018804), 
>>>
>>>is about the same size as the nth term of sequence A006218, sum_(k=1 .  . 
>>>n) d (k ) (corresponding terms are 1, 3, 5, 8, 10, 14, 16, 20, 23, 27 . . 
>>>. ; see http://www.research.att.com/projects/OEIS?Anum=A006218), 
>>>
>>>or "about" n* (ln (n ) + 2*c - 1?
>...

I wrote:
>>A possible start for now.
>>(math below figured uncarefully)
>>
>>
>>
>>sum{k=1 to n} GCD(k,n) =
>>
>>n *sum{k|n} phi(k) /k,
>>
>>I think.
>>
>[rest snipped]
>
>Okay, this is along the very lines of what I have been interested in 
>lately.
>
>
>Since sum{k|n} phi(k) = n,
>
>we can write the above as, for n = 6 as an example:
>
>
>n * (1 + 1/2 + 1/3 + 1/3 + 1/6 + 1/6),
>
>so, for whatever n, we have 1/k written phi(k) times.
>
>(By the way, I forgot to define phi as the Euler totient function, the 
>number of positive integers coprime with k and <= k.)
>
>So, if we subtracted H(n) = 1 + 1/2 + 1/3+...+1/n, the n_th harmonic 
>number, times n, we would have, for n = 6,
>
>6 *(1 -1 +1/2 -1/2 + 1/3 -1/3 + 1/3 -1/4 + 1/6 - 1/5 + 1/6 - 1/6).
>
>So we have a finite sum in the parentheses where we have:
>
>sum{k=1 to n} (1/j(k) - 1/k), where j(k) is the k_th term which is added 
>(which is a divisor of n).
>
>
>Now,
>0 <= |1/j(k) - 1/k|  <= |2/n -1/(n-1)| < 1/n.
>
>(I am uncertain about that upper bound.)
>




Whatever that upper bound really is, it is certainly <= 1/k.

So, 

sum{k=1 to n} GCD(k,n) = O(n ln(n)),

if it is not simply  ~ n ln(n).


(Right?)


Leroy


>So, 
>
>sum{k=1 to n} GCD(k,n) /n   - H(n) < 1.
>
>(where the '<' is not exactly a tight inequality most of the time, I 
>would bet).
>
>So, at the very least,
>
>since H(n) ~ ln(n) + .5772...,
>
>limit{n->oo}
>(sum{k=1 to n} GCD(k,n))/(n * ln(n)) = 1,
>
>(If the limit exists, which I bet it does.)
>
>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?
>
>thanks,
>Leroy Quet
>
>