A060367 Average order of an element in a cyclic group of order n rounded down.
1, 1, 2, 2, 4, 3, 6, 5, 6, 6, 10, 6, 12, 9, 9, 10, 16, 10, 18, 11, 14, 15, 22, 12, 20, 18, 20, 16, 28, 14, 30, 21, 23, 24, 25, 18, 36, 27, 28, 22, 40, 21, 42, 27, 28, 33, 46, 24, 42, 31, 37, 33, 52, 30, 42, 33, 42, 42, 58, 26, 60, 45, 41, 42, 50, 35, 66, 44, 51
Offset: 1
Links
- Danny Rorabaugh, Table of n, a(n) for n = 1..10000
Programs
-
Maple
seq(floor(numtheory:-sigma[2](n^2)/numtheory:-sigma(n^2)/n), n=1..1000); # Robert Israel, Mar 24 2015
-
Mathematica
f[n_] := Block[{i, j, k}, Reap@ For[j = 1, j <= n, j++, Sow[Floor[Sum[1/GCD[j, k], {k, 1, j}]]]]] // Flatten // Rest; f@ 49 (* Michael De Vlieger, Mar 24 2015 *) a[n_] := Floor[DivisorSigma[2, n^2]/DivisorSigma[1, n^2]/n]; Array[a, 100] (* Amiram Eldar, Jul 25 2025 *) -
PARI
a(n) = {my(f = factor(n^2)); floor(sigma(f, 2)/(n * sigma(f)));} \\ Amiram Eldar, Jul 25 2025 -
Sage
[floor(sum([1/gcd(n,k) for k in range(1,n+1)])) for n in range(1,50)] # Danny Rorabaugh, Mar 24 2015
Formula
Sequence A057660 gives the sum of the orders of the elements in a cyclic group with n elements so a(n) = floor(A057660(n) / n) = floor(Sum_{k=1..n} 1/GCD(n, k)) = floor(Sum of 1/d times phi(n/d)) for all divisors d of n, where phi is Euler's phi function. This sum may also be expressed as the product of (p^(2*e(p)+1)+1)/((p+1)*p^e(p)) over all prime divisors p of n where the canonical factorization of n is the product of p^e(p), the e(p) being the exponents of the power of p in the factorization.
From Amiram Eldar, Jul 25 2025: (Start)
a(n) = floor(sigma_2(n^2)/(n*sigma(n))) = floor(A001157(n^2)/(n*A000203(n^2))) = floor(A065827(n)/(n*A065764(n))).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = zeta(3)/zeta(2) (A253905). (End)
Extensions
Offset corrected and terms a(18)-a(50) added by Danny Rorabaugh, Mar 24 2015