|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Avi Peretz (njk(AT)netvision.net.il), Apr 01 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|