%I #23 Dec 07 2021 11:08:46
%S 0,3,1,7,1,7,1,15,1,7,1,15,1,7,3,15,1,7,1,15,3,7,1,31,1,7,1,15,1,15,1,
%T 15,3,7,3,15,1,7,3,31,1,15,1,15,3,7,1,31,1,7,3,15,1,7,3,31,3,7,1,31,1,
%U 7,3,15,3,15,1,15,3,15,1,31,1,7,3,15,3,15,1
%N Number of elements of order 2 in the group SL(2, Z(n)).
%C Equivalently, the number of cyclic subgroups of the group SL(2, Z(n)) having order 2, counting conjugates as distinct.
%H Antti Karttunen, <a href="/A316553/b316553.txt">Table of n, a(n) for n = 1..1023</a>
%F Conjecture: a(n) = 2^(omega(n) + min(3, valuation(n, 2))) - 1.
%F From _Robert Israel_, Jun 15 2020: (Start)
%F Number of solutions mod n, other than t[1]=t[4]=1,t[2]=t[3]=0, of the equations t[2]*(t[1] + t[4])=0, t[3]*(t[1] + t[4])=0, t[1]^2 + t[2]*t[3] = 1, t[2]*t[3] + t[4]^2 = 1, t[1]*t[4] - t[2]*t[3] = 1.
%F If m and n are coprime, a(m*n) = a(m)*a(n)+a(m)+a(n) (i.e. a(n)+1 is multiplicative).
%F If n > 1 is in A061345, a(n)=1. (End)
%e Case n=2: the three 2 X 2 matrices on Z(2) having determinant 1 and order 2 are:
%e [ 0 1 ] [ 1 0 ] [ 1 1 ]
%e [ 1 0 ] [ 1 1 ] [ 0 1 ]
%o (GAP) Concatenation([0], List([2..10], n->Sum(Filtered( ConjugacyClassesSubgroups( SL(2, Integers mod n)), x->Order( Representative(x))=2 and IsCyclic( Representative(x))), Size)));
%o (PARI) a(n)={my(id=matid(2)); sum(a=0, n-1, sum(b=0, n-1, sum(c=0, n-1, sum(d=0, n-1, my(M=Mod([a, b; c, d], n)); if(matdet(M)==1, M^2==id))))) - 1}
%o (PARI)
%o memoA316553 = Map(); \\ Only values at 2^k are actually collected here.
%o A316553slow_memoized(n) = if(1==n, 0, if((n%2)&&isprimepower(n), 1, my(id=matid(2), v); if(mapisdefined(memoA316553,n,&v), v, v = (sum(a=0, n-1, sum(b=0, n-1, sum(c=0, n-1, sum(d=0, n-1, my(M=Mod([a, b; c, d], n)); if(matdet(M)==1, M^2==id))))) - 1); mapput(memoA316553,n,v); (v))));
%o A316553(n) = if(1==n,0,my(f=factor(n)); -1 + prod(i=1,#f~,1+A316553slow_memoized(f[i,1]^f[i,2]))); \\ (Based on _Robert Israel_'s multiplicativity rule) - _Antti Karttunen_, Dec 05 2021
%Y Column 2 of A316564.
%Y Cf. A174275, A316537.
%Y Cf. A061345.
%K nonn
%O 1,2
%A _Andrew Howroyd_, Jul 06 2018
|