Question about A018804

[Leroy Quet]

>
>On 1 December, Leroy Quet wrote:
>
>I figured (and Martin Cohen confirmed {referencing Hardy & Wright theorem 
>320}) that d(m), the number of positive divisors of m, was such that
>
>limit{n-> infinity} (1/n) (sum{m=1 to n} d(m))   - ln(n)
>
>= 2*c - 1, where c is Euler's constant (.5772...).
>
>
>******* 
>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?
>
>Put more technically, does 
>limit {n -> infinity}  sum_(k=1 . . . n) A018804(k )/ sum_(k=1 . . . n) 
>A006218(k )
>=1 (or possibly slightly more or less than 1)?
>
>I can see why this might be true (since A006218 is also sum_(k=1 . . . n) 
>floor (n/k) ),  but proving it is beyond me.  Thanks in advance to anyone 
>who might reply to this query. 
>
>Regards,
>Matthew Vandermast


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.

And this is 
 sum{k|n} mu(n/k) d(k) k

(where mu() is Mobius function).

So,
 (1/n) sum{m|n} (sum{k=1 to m} GCD(k,m)) =

d(n).

(Using just the 
n *sum{k|n} phi(k) /k
result might most likely be the path through this maze...)


thanks,
Leroy Quet