A322168 - OEIS

%I #78 Dec 15 2024 07:22:06

%S 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 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 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 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 Here A,B,C,D are positive integers, in Z+, satisfying A*D-B*C=1.

%C 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 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 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 James Kirk Winkler, <a href="/A322168/b322168.txt">Table of n, a(n) for n = 1..8191</a>

%e row 1: [[1,0],[0,1]]   trace = 2

%e row 2: [[1,0],[1,1]], [[1,1],[0,1]]   trace = 2, 2

%e row 3: [[1,0],[2,1]], [[1,1],[1,2]], [[2,1],[1,1]], [[1,2],[0,1]]   trace = 2, 3, 3, 2

%e ...

%e Sum the matrix rows for the Stern-Brocot tree.

%e row 1: 1/1

%e row 2: 1/2, 2/1

%e row 3: 1/3, 2/3, 3/2, 3/1

%e ...

%t 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 Array[row, 7] // Flatten (* _Jean-François Alcover_, Dec 17 2018, after _Andrew Howroyd_ *)

%o (Python)

%o def mul(A, B):

%o     a = A[0]*B[0] + A[1]*B[2]

%o     b = A[0]*B[1] + A[1]*B[3]

%o     c = A[2]*B[0] + A[3]*B[2]

%o     d = A[2]*B[1] + A[3]*B[3]

%o     return([a, b, c, d])

%o I = [1, 0, 0, 1]

%o L = [1, 0, 1, 1]

%o R = [1, 1, 0, 1]

%o slg = [I]

%o a_lst = slg

%o for n in range(12):

%o     b_lst = []

%o     for ele in a_lst:

%o         b_lst.append(mul(ele, L))

%o         b_lst.append(mul(ele, R))

%o     a_lst = b_lst

%o     for ele in b_lst:

%o         slg.append(ele)

%o seq = []

%o for ele in slg:

%o     seq.append(ele[0]+ele[3])

%o (PARI)

%o 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 { for(n=1, 7, print(row(n))) } \\ _Andrew Howroyd_, Dec 12 2018

%K nonn,tabf

%O 1,1

%A _James Kirk Winkler_, Dec 11 2018