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
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.
Programs
-
Haskell
a036391 = sum . a139366_row -- Reinhard Zumkeller, May 01 2013
-
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 *)
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
Extensions
Adapted to the definition: a(1)=0 by Alois P. Heinz, Oct 28 2012
Comments