cp's OEIS Frontend

A322168 Sequence gives the values of the trace A+D of the 2 X 2 matrices [[A,B],[C,D]] in a binary tree of the special linear monoid, SL(2,Z+).

%I A322168 #78 Dec 15 2024 07:22:06
%S A322168 2,2,2,2,3,3,2,2,4,4,4,4,4,4,2,2,5,5,6,5,7,6,5,5,6,7,5,6,5,5,2,2,6,6,
%T A322168 8,6,10,8,8,6,10,10,10,8,10,8,6,6,8,10,8,10,10,10,6,8,8,10,6,8,6,6,2,
%U A322168 2,7,7,10,7,13,10,11,7,14,13,15,10,15,11,10,7,13,14,15,13,18,15,13,10,15,15,14,11,13,10,7,7,10,13,11,14,15,15,10,13,15,18,13,15,14,13,7,10,11,15,10,15,13,14,7,11,10,13,7,10,7,7,2
%N A322168 Sequence gives the values of the trace A+D of the 2 X 2 matrices [[A,B],[C,D]] in a binary tree of the special linear monoid, SL(2,Z+).
%C A322168 Here A,B,C,D are positive integers, in Z+, satisfying A*D-B*C=1.
%C A322168 The SL(2,Z+) monoid may be constructed as a binary tree by starting with the identity matrix, I = [[1,0],[0,1]], then multiply by L = [[1,0],[1,1]] and R = [[1,1],[0,1]] creating the 2nd row in the tree.  Multiplying the two elements of the 2nd row by L and R creates the 3rd row.  Repeat for each row.  See the Python program.
%C A322168 The monoid SL(2,Z+) is isomorphic to the positive rationals Q+.  The sum of the rows of an SL(2,Z+) element create a unique reduced fraction, p/q.:   [[a,b],[c,d]] => (a+b)/(c+d) = p/q   These fractions map to the entries of the Stern-Brocot tree.
%C A322168 SL(2,Z+) is a sub-monoid of SL(2,Z). The generators of SL(2,Z) are [[0,-1],[1,0]] and [[1,1],[0,1]].  The author believes that L and R are generators for SL(2,Z+) and all elements of the monoid are present in the tree.
%H A322168 James Kirk Winkler, <a href="/A322168/b322168.txt">Table of n, a(n) for n = 1..8191</a>
%e A322168 row 1: [[1,0],[0,1]]   trace = 2
%e A322168 row 2: [[1,0],[1,1]], [[1,1],[0,1]]   trace = 2, 2
%e A322168 row 3: [[1,0],[2,1]], [[1,1],[1,2]], [[2,1],[1,1]], [[1,2],[0,1]]   trace = 2, 3, 3, 2
%e A322168 ...
%e A322168 Sum the matrix rows for the Stern-Brocot tree.
%e A322168 row 1: 1/1
%e A322168 row 2: 1/2, 2/1
%e A322168 row 3: 1/3, 2/3, 3/2, 3/1
%e A322168 ...
%t A322168 row[n_] := Module[{v = Table[0, {2^(n-1)}], L = {{1, 0}, {1, 1}}}, For[k = 0, k <= Length[v]-1, k++, v[[k+1]] = Tr[Dot @@ Table[If[BitGet[k, b] == 1, Transpose[L], L], {b, 0, n-2}]]]; v]; row[1] = {2};
%t A322168 Array[row, 7] // Flatten (* _Jean-François Alcover_, Dec 17 2018, after _Andrew Howroyd_ *)
%o A322168 (Python)
%o A322168 def mul(A, B):
%o A322168     a = A[0]*B[0] + A[1]*B[2]
%o A322168     b = A[0]*B[1] + A[1]*B[3]
%o A322168     c = A[2]*B[0] + A[3]*B[2]
%o A322168     d = A[2]*B[1] + A[3]*B[3]
%o A322168     return([a, b, c, d])
%o A322168 I = [1, 0, 0, 1]
%o A322168 L = [1, 0, 1, 1]
%o A322168 R = [1, 1, 0, 1]
%o A322168 slg = [I]
%o A322168 a_lst = slg
%o A322168 for n in range(12):
%o A322168     b_lst = []
%o A322168     for ele in a_lst:
%o A322168         b_lst.append(mul(ele, L))
%o A322168         b_lst.append(mul(ele, R))
%o A322168     a_lst = b_lst
%o A322168     for ele in b_lst:
%o A322168         slg.append(ele)
%o A322168 seq = []
%o A322168 for ele in slg:
%o A322168     seq.append(ele[0]+ele[3])
%o A322168 (PARI)
%o A322168 row(n)={my(v=vector(2^(n-1)), L=[1,0;1,1]); for(k=0, #v-1, v[k+1]=trace(prod(b=0, n-2, if(bittest(k,b), L~, L)))); v}
%o A322168 { for(n=1, 7, print(row(n))) } \\ _Andrew Howroyd_, Dec 12 2018
%K A322168 nonn,tabf
%O A322168 1,1
%A A322168 _James Kirk Winkler_, Dec 11 2018