%I #34 Aug 02 2023 09:36:41
%S 0,1,3,3,11,3,21,7,21,11,63,7,77,21,23,23,171,21,183,23,49,63,333,15,
%T 231,77,183,49,473,23,441,87,147,171,161,49,671,183,161,47,903,49,903,
%U 147,161,333,1521,47,903,231,343,161,1727,183,483,105,427,473,2439,47
%N a(n) = sum of order of a mod n, 0 < a < n, gcd(a, n) = 1.
%C Related to a problem of Arnold.
%C Row sums of triangle A139366. - _Wolfdieter Lang_, Sep 09 2008
%H Alois P. Heinz, <a href="/A036391/b036391.txt">Table of n, a(n) for n = 1..2000</a>
%H Pär Kurlberg and Carl Pomerance, <a href="http://arxiv.org/abs/1108.5209">On a problem of Arnold: the average multiplicative order of a given integer</a>, arXiv:1108.5209 [math.NT], 2012.
%F 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
%F If n is in A033948 then a(n) = Sum_{divisors d of phi(n)} phi(d)*d. - _Geoffrey Critzer_, Jan 24 2015
%p with(numtheory):
%p a:= n-> add(`if`(igcd(n, k)=1, order(k, n), 0), k=1..n-1):
%p seq(a(n), n=1..60); # _Alois P. Heinz_, Oct 28 2012
%t 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 *)
%o (Haskell)
%o a036391 = sum . a139366_row -- _Reinhard Zumkeller_, May 01 2013
%K nonn,nice
%O 1,3
%A _David W. Wilson_
%E Adapted to the definition: a(1)=0 by _Alois P. Heinz_, Oct 28 2012