OFFSET
1,1
COMMENTS
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.
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Boston, 2nd Ed., 12th printing, 2002, pp. 24-25.
P. Lancaster and M. Tismenetsky, The Theory of Matrices, Academic Press, Boston, 1985, p. 35.
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.
LINKS
Nei Y. Soma, Rows n = 1..30, flattened
K. Sutner, Linear Cellular Automata and the Garden-of-Eden, The Mathematical Intelligencer, 11(2), 1989, pp. 49-53; see p. 52
FORMULA
The recurrence has as its base:
r(1, 1) = 11;
r(2, 1) = 3;
r(3, 1) = 12;
r(4, 1) = 13.
For 2 <= k <= m, and i = 1, 2, 3, ..., 3k - 2:
r(i, k) = 8*r(i, k-1) + r(2, 1) (i != 0 (mod 3)).
And r(3k-1, k) = r(2, 1);
r(3k, k) = 8*r(3(k-1), k-1) + r(3,1);
r(3k+1, k) = 8*r(3(k-1), k-1) + r(4,1).
EXAMPLE
For m = 1, the Jacobi 4 X 4 matrix has as rows
1, 1, 0, 0
1, 1, 1, 0
0, 1, 1, 1
0, 0, 1, 1
Its inverse has the rows
1, 0, 1, 1
0, 0, 1, 1
1, 1, 0, 0
1, 1, 0, 1
Representing these rows as binary numbers in base 10 the first three terms of the sequence are: 11, 3, 12, 13.
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:
1, 1, 0, 0, 0, 0, 0
1, 1, 1, 0, 0, 0, 0
0, 1, 1, 1, 0, 0, 0
0, 0, 1, 1, 1, 0, 0
0, 0, 0, 1, 1, 1, 0
0, 0, 0, 0, 1, 1, 1
0, 0, 0, 0, 0, 1, 1
Its inverse has as rows:
1, 0, 1, 1, 0, 1, 1
0, 0, 1, 1, 0, 1, 1
1, 1, 0, 0, 0, 0, 0
1, 1, 0, 1, 0, 1, 1
0, 0, 0, 0, 0, 1, 1
1, 1, 0, 1, 1, 0, 0
1, 1, 0, 1, 1, 0, 1
These 7 latter rows from binary to base 10 give the next 7 terms of the sequence: 91, 27, 96, 107, 3, 108, 109.
Triangle T(n,k) begins:
11, 3, 12, 13;
91, 27, 96, 107, 3, 108, 109;
731, 219, 768, 859, 27, 864, 875, 3, 876, 877;
5851, 1755, 6144, 6875, 219, 6912, 7003, 27, 7008, 7019, 3, 7020, 7021;
...
MAPLE
T:= n-> (M-> seq(add(abs(M[j, n*3+1-i])*2^i, i=0..n*3), j=1..n*3+1))
(Matrix(n*3+1, (i, j)-> `if`(abs(i-j)<2, 1, 0))^(-1)):
seq(T(n), n=1..6); # Alois P. Heinz, May 20 2023
MATHEMATICA
sequence = {};
For[k = 1, k <= 50, k++, {
n = 3*k + 1;
J = ConstantArray[0, {n, n}];
For[i = 1, i < n, i++,
J[[i, i]] = J[[i + 1, i]] = J[[i, i + 1]] = 1];
J[[1, 1]] = J[[n, n]] = 1;
InvJ = Mod[Inverse[J], 2];
For[i = 1, i <= n, i++, AppendTo[sequence, FromDigits[InvJ[[i]], 2]]]
}
]
sequence
PROG
(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
CROSSREFS
Column k=1 gives A245599(n+1).
Column k=2 gives A083713.
Column k=3 gives A204623.
T(n,3n-1) gives A010701.
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).
KEYWORD
nonn,base,tabf
AUTHOR
Nei Y. Soma, May 20 2023
STATUS
approved