Question about A018804
Leroy Quet
qq-quet at mindspring.com
Wed Dec 3 03:28:01 CET 2003
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
More information about the SeqFan
mailing list