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,3

Links

Danny Rorabaugh, Table of n, a(n) for n = 1..10000

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)

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 *)

Prog

(SageMath) [floor(sum([1/gcd(n, k) for k in range(1, n+1)])) for n in range(1, 50)] # Danny Rorabaugh, Mar 24 2015
(PARI) a(n) = {my(f = factor(n^2)); floor(sigma(f, 2)/(n * sigma(f))); } \\ Amiram Eldar, Jul 25 2025

Crossrefs

Cf. A000010, A000203, A001157, A018804, A057660, A065764, A065827, A253905.

Sequence in context: A368582 A352956 A304214 * A267451 A062968 A239966

Adjacent sequences: A060364 A060365 A060366 * A060368 A060369 A060370

Keyword

nonn,easy

Author

Avi Peretz (njk(AT)netvision.net.il), Apr 01 2001

Extensions

Offset corrected and terms a(18)-a(50) added by Danny Rorabaugh, Mar 24 2015

Status

approved