A363099 - OEIS

%I #51 May 25 2023 15:12:41

%S 11,3,12,13,91,27,96,107,3,108,109,731,219,768,859,27,864,875,3,876,

%T 877,5851,1755,6144,6875,219,6912,7003,27,7008,7019,3,7020,7021,46811,

%U 14043,49152,55003,1755,55296,56027,219,56064,56155,27,56160,56171,3,56172,56173,374491,112347,393216,440027,14043,442368

%N Triangle T(n,k) in which the n-th row encodes the inverse of a 3n+1 X 3n+1 Jacobi matrix, with 1's on the lower, main, and upper diagonals in GF(2), where the encoding consists of the decimal representations for the binary rows (n >= 1, 1 <= k <= 3n+1).

%C Each term in the sequence encodes a line of the inverse of a Jacobi matrix that has 1s on its lower, main, and upper diagonals in GF(2). The associated inverse matrix column values come from the binary representation of that base-10 number, being a bit per column. These matrices start with a 4 X 4 matrix and the consecutive terms came by adding ascending and consecutive multiples of 3. If the binary number has fewer bits than the number of columns, it must be zero-padded to the left. To obtain the inverse matrices in real numbers instead of GF(2), alternate between + and - between the 1s in a row. If a row is a multiple of 3, alternate between - and +. The determinants of these 3m+1 X 3m+1 Jacobi matrices are 1 in GF(2), and alternate between -1 and 1 in R if m is odd or even. These properties were proven by Sutner (1989) and Melo (1997), respectively.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Boston, 2nd Ed., 12th printing, 2002, pp. 24-25.

%D P. Lancaster and M. Tismenetsky, The Theory of Matrices, Academic Press, Boston, 1985, p. 35.

%D J. P. Melo, Reversibility of John von Neumann cellular automata, M.Sc. Thesis, Division of Computer Science, Instituto Tecnológico de Aeronáutica, 1997 (in Portuguese), p. 18.

%H Nei Y. Soma, <a href="/A363099/b363099.txt">Rows n = 1..30, flattened</a>

%H K. Sutner, <a href="https://www.link.cs.cmu.edu/15859-s11/notes/sutner.pdf">Linear Cellular Automata and the Garden-of-Eden</a>, The Mathematical Intelligencer, 11(2), 1989, pp. 49-53; see p. 52

%F The recurrence has as its base:

%F      r(1, 1) = 11;

%F      r(2, 1) =  3;

%F      r(3, 1) = 12;

%F      r(4, 1) = 13.

%F For 2 <= k <= m, and i = 1, 2, 3, ..., 3k - 2:

%F     r(i, k) = 8*r(i, k-1) + r(2, 1) (i != 0 (mod 3)).

%F And r(3k-1, k) = r(2, 1);

%F     r(3k,   k) = 8*r(3(k-1), k-1) + r(3,1);

%F     r(3k+1, k) = 8*r(3(k-1), k-1) + r(4,1).

%e For m = 1, the Jacobi 4 X 4 matrix has as rows

%e      1, 1, 0, 0

%e      1, 1, 1, 0

%e      0, 1, 1, 1

%e      0, 0, 1, 1

%e Its inverse has the rows

%e      1, 0, 1, 1

%e      0, 0, 1, 1

%e      1, 1, 0, 0

%e      1, 1, 0, 1

%e Representing these rows as binary numbers in base 10 the first three terms of the sequence are: 11, 3, 12, 13.

%e The next numbers in the sequence occur for m = 2, given a sequence of six numbers. The Jacobi 7 X 7 matrix has as its rows:

%e      1, 1, 0, 0, 0, 0, 0

%e      1, 1, 1, 0, 0, 0, 0

%e      0, 1, 1, 1, 0, 0, 0

%e      0, 0, 1, 1, 1, 0, 0

%e      0, 0, 0, 1, 1, 1, 0

%e      0, 0, 0, 0, 1, 1, 1

%e      0, 0, 0, 0, 0, 1, 1

%e Its inverse has as rows:

%e      1, 0, 1, 1, 0, 1, 1

%e      0, 0, 1, 1, 0, 1, 1

%e      1, 1, 0, 0, 0, 0, 0

%e      1, 1, 0, 1, 0, 1, 1

%e      0, 0, 0, 0, 0, 1, 1

%e      1, 1, 0, 1, 1, 0, 0

%e      1, 1, 0, 1, 1, 0, 1

%e These 7 latter rows from binary to base 10 give the next 7 terms of the sequence: 91, 27, 96, 107, 3, 108, 109.

%e Triangle T(n,k) begins:

%e     11,    3,   12,   13;

%e     91,   27,   96,  107,   3,  108,  109;

%e    731,  219,  768,  859,  27,  864,  875,  3,  876,  877;

%e   5851, 1755, 6144, 6875, 219, 6912, 7003, 27, 7008, 7019, 3, 7020, 7021;

%e   ...

%p T:= n-> (M-> seq(add(abs(M[j, n*3+1-i])*2^i, i=0..n*3), j=1..n*3+1))

%p                (Matrix(n*3+1, (i, j)-> `if`(abs(i-j)<2, 1, 0))^(-1)):

%p seq(T(n), n=1..6);  # _Alois P. Heinz_, May 20 2023

%t sequence = {};

%t For[k = 1, k <= 50, k++, {

%t   n = 3*k + 1;

%t   J = ConstantArray[0, {n, n}];

%t   For[i = 1, i < n, i++,

%t    J[[i, i]] = J[[i + 1, i]] = J[[i, i + 1]] = 1];

%t   J[[1, 1]] = J[[n, n]] = 1;

%t   InvJ = Mod[Inverse[J], 2];

%t   For[i = 1, i <= n, i++, AppendTo[sequence, FromDigits[InvJ[[i]], 2]]]

%t   }

%t  ]

%t sequence

%o (PARI) row(n)=my(m=3*n+1, A=lift(matrix(m, m, i, j, Mod(abs(i-j)<=1, 2))^(-1))); vector(m, i, fromdigits(A[i,], 2)) \\ _Andrew Howroyd_, May 20 2023

%Y Column k=1 gives A245599(n+1).

%Y Column k=2 gives A083713.

%Y Column k=3 gives A204623.

%Y T(n,3n-1) gives A010701.

%Y Cf. A038184 One-dimensional cellular automaton (Rule 150) in a tape with 3m cells has as adjacency matrix the Jacobi matrices, 3m X 3m, with 1s on the lower, main and upper diagonals and the operations on it are in GF(2). And A363146 for the inverse of Jacobi matrices 3m X 3m, with 1s on the lower, main, and upper diagonals in GF(2).

%K nonn,base,tabf

%O 1,1

%A _Nei Y. Soma_, May 20 2023