Question about A018804

[Leroy Quet]

I forgot to give credit to Matthew Vandermast 
in my last reply for the original email.

My reply below.


Matthew wrote:
>>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.
>
[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.)

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