%I M3946 #38 Jan 28 2021 21:35:49
%S 1,26,272,722,5270,5260,37358,18414,56216,95668,487714,99796,1304262,
%T 627046,593398,481982,7044222,931396,11570384,1602940,4037650,8694134,
%U 40220524,2069292,15855230,21686124,13215872,10948486,129952894,10451648
%N Sum of orders of all 2 X 2 matrices with entries mod n.
%C The order of a matrix M over Z/(nZ) is the smallest k such that M^k is idempotent.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Michael S. Branicky, <a href="/A006045/b006045.txt">Table of n, a(n) for n = 1..150</a> (first 61 terms from _Sean A. Irvine_)
%H Michael S. Branicky, <a href="/A006045/a006045.py.txt">Python program</a>
%H A. Wilansky, <a href="https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/AlbertWilansky.pdf">Spectral decomposition of matrices for high school students</a>, Math. Mag., vol. 41, 1968, pp. 51-59.
%H A. Wilansky, <a href="/A006045/a006045_1.pdf">Spectral decomposition of matrices for high school students</a>, Math. Mag., vol. 41, 1968, pp. 51-59. (Annotated scanned copy)
%H A. Wilansky, <a href="/A006045/a006045.pdf">Letters to N. J. A. Sloane, Jun. 1991</a>.
%o (PARI) order(m) = {kk = 1; ok = 0; while (! ok, mk = m^kk; if (mk^2 == mk, ok = 1, kk++);); return(kk);}
%o a(n) = {ret = 0; m = matrix(2, 2); for (i=0, n-1, m[1, 1] = Mod(i, n); for (j=0, n-1, m[1, 2] = Mod(j, n); for (k=0, n-1, m[2, 1] = Mod(k, n); for (l=0, n-1, m[2, 2] = Mod(l, n); ret += order(m););););); return (ret);}
%o (Python) # see link for faster version
%o from itertools import product
%o def mmm2(A, B, modder): # matrix multiply modulo for 2x2
%o return ((A[0]*B[0]+A[1]*B[2])%modder, (A[0]*B[1]+A[1]*B[3])%modder,
%o (A[2]*B[0]+A[3]*B[2])%modder, (A[2]*B[1]+A[3]*B[3])%modder)
%o def order(A, modder):
%o Ak, k = A, 1
%o while mmm2(Ak, Ak, modder) != Ak: Ak, k = mmm2(Ak, A, modder), k+1
%o return k
%o def a(n): return sum(order(A, n) for A in product(range(n), repeat=4))
%o print([a(n) for n in range(1, 12)]) # _Michael S. Branicky_, Jan 26 2021
%K nonn
%O 1,2
%A _N. J. A. Sloane_, Albert Wilansky
%E The article gives an incorrect value for a(5).
%E More terms from _Michel Marcus_, Jun 07 2013
%E More terms from _Sean A. Irvine_, Dec 18 2016
|