OFFSET
1,2
COMMENTS
Equivalently, the number of cyclic subgroups of the group SL(2, Z(n)) having order 2, counting conjugates as distinct.
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..1023
FORMULA
Conjecture: a(n) = 2^(omega(n) + min(3, valuation(n, 2))) - 1.
From Robert Israel, Jun 15 2020: (Start)
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.
If m and n are coprime, a(m*n) = a(m)*a(n)+a(m)+a(n) (i.e. a(n)+1 is multiplicative).
If n > 1 is in A061345, a(n)=1. (End)
EXAMPLE
Case n=2: the three 2 X 2 matrices on Z(2) having determinant 1 and order 2 are:
[ 0 1 ] [ 1 0 ] [ 1 1 ]
[ 1 0 ] [ 1 1 ] [ 0 1 ]
PROG
(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)));
(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}
(PARI)
memoA316553 = Map(); \\ Only values at 2^k are actually collected here.
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))));
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Jul 06 2018
STATUS
approved