A036391 a(n) = sum of order of a mod n, 0 < a < n, gcd(a, n) = 1.

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

Alois P. Heinz, Table of n, a(n) for n = 1..2000

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

Adjacent sequences: A036388 A036389 A036390 * A036392 A036393 A036394

Keyword

nonn,nice

Author

David W. Wilson

Extensions

Adapted to the definition: a(1)=0 by Alois P. Heinz, Oct 28 2012

Status

approved