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+).

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, 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, 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

Offset

1,1

Comments

Here A,B,C,D are positive integers, in Z+, satisfying A*D-B*C=1.

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.

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.

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.

Links

James Kirk Winkler, Table of n, a(n) for n = 1..8191

Example

row 1: [[1,0],[0,1]]   trace = 2
row 2: [[1,0],[1,1]], [[1,1],[0,1]]   trace = 2, 2
row 3: [[1,0],[2,1]], [[1,1],[1,2]], [[2,1],[1,1]], [[1,2],[0,1]]   trace = 2, 3, 3, 2
...
Sum the matrix rows for the Stern-Brocot tree.
row 1: 1/1
row 2: 1/2, 2/1
row 3: 1/3, 2/3, 3/2, 3/1
...

Mathematica

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};
Array[row, 7] // Flatten (* Jean-François Alcover, Dec 17 2018, after Andrew Howroyd *)

Prog

(Python)
def mul(A, B):
    a = A[0]*B[0] + A[1]*B[2]
    b = A[0]*B[1] + A[1]*B[3]
    c = A[2]*B[0] + A[3]*B[2]
    d = A[2]*B[1] + A[3]*B[3]
    return([a, b, c, d])
I = [1, 0, 0, 1]
L = [1, 0, 1, 1]
R = [1, 1, 0, 1]
slg = [I]
a_lst = slg
for n in range(12):
    b_lst = []
    for ele in a_lst:
        b_lst.append(mul(ele, L))
        b_lst.append(mul(ele, R))
    a_lst = b_lst
    for ele in b_lst:
        slg.append(ele)
seq = []
for ele in slg:
    seq.append(ele[0]+ele[3])
(PARI)
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}
{ for(n=1, 7, print(row(n))) } \\ Andrew Howroyd, Dec 12 2018

Crossrefs

Sequence in context: A367008 A366800 A366799 * A118377 A023516 A156607

Adjacent sequences: A322165 A322166 A322167 * A322169 A322170 A322171

Keyword

nonn,tabf

Author

James Kirk Winkler, Dec 11 2018

Status

approved