# Python program (3.6) by Michael S. Branicky, Jan 26 2021
#A006045 Sum of orders of all 2 X 2 matrices with entries mod n.

# (Python)
from numba import njit
from itertools import product
@njit
def mmm2(A, B, modder): # matrix multiply modulo for 2x2
  return ((A[0]*B[0]+A[1]*B[2])%modder, (A[0]*B[1]+A[1]*B[3])%modder,
          (A[2]*B[0]+A[3]*B[2])%modder, (A[2]*B[1]+A[3]*B[3])%modder)
@njit 
def order(A, modder):
  Ak, k = A, 1
  while mmm2(Ak, Ak, modder) != Ak: Ak, k = mmm2(Ak, A, modder), k+1
  return k
@njit
def a(n): 
  s = 0
  for a in range(n):
    for b in range(n):
      for c in range(b, n): # by symmetry
        for d in range(n):
          if c == b:
            s += order((a, b, c, d), n)
          else:
            s += 2*order((a, b, c, d), n) # by symmetry
  return s  
print([a(n) for n in range(1, 31)]) # ~~~~

print()
# generate b-file
from time import time
time0 = time()
for n in range(1, 10001):
  an = a(n)
  print(n, an, time()-time0, flush=True)
  with open('b006045.txt', 'a') as f:
    f.write(f"{n} {an}\n")