# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a006045
Showing 1-1 of 1

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

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE