

A060367


Average order of an element in a cyclic group of order n rounded down.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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.


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


PROG

(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


CROSSREFS

Cf. A057660, A018804.
Sequence in context: A029578 A054345 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, Danny Rorabaugh, Mar 24 2015


STATUS

approved



