login
A036391
a(n) = sum of order of a mod n, 0 < a < n, gcd(a, n) = 1.
6
0, 1, 3, 3, 11, 3, 21, 7, 21, 11, 63, 7, 77, 21, 23, 23, 171, 21, 183, 23, 49, 63, 333, 15, 231, 77, 183, 49, 473, 23, 441, 87, 147, 171, 161, 49, 671, 183, 161, 47, 903, 49, 903, 147, 161, 333, 1521, 47, 903, 231, 343, 161, 1727, 183, 483, 105, 427, 473, 2439, 47
OFFSET
1,3
COMMENTS
Related to a problem of Arnold.
Row sums of triangle A139366. - Wolfdieter Lang, Sep 09 2008
LINKS
Pär Kurlberg and Carl Pomerance, On a problem of Arnold: the average multiplicative order of a given integer, arXiv:1108.5209 [math.NT], 2012.
FORMULA
On the GRH, Kurlberg & Pomerance show that a(n) = n^2/log n exp(B log log n/log log log n (1 + o(1))), where B = A218342 = 0.345372.... - Charles R Greathouse IV, Oct 26 2012
If n is in A033948 then a(n) = Sum_{divisors d of phi(n)} phi(d)*d. - Geoffrey Critzer, Jan 24 2015
MAPLE
with(numtheory):
a:= n-> add(`if`(igcd(n, k)=1, order(k, n), 0), k=1..n-1):
seq(a(n), n=1..60); # Alois P. Heinz, Oct 28 2012
MATHEMATICA
a[n_] := Sum[ If[ CoprimeQ[k, n], MultiplicativeOrder[k, n], 0], {k, 1, n-1}]; Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Aug 19 2013 *)
PROG
(Haskell)
a036391 = sum . a139366_row -- Reinhard Zumkeller, May 01 2013
CROSSREFS
Sequence in context: A265390 A276390 A178707 * A283138 A262528 A359685
KEYWORD
nonn,nice
EXTENSIONS
Adapted to the definition: a(1)=0 by Alois P. Heinz, Oct 28 2012
STATUS
approved