A125837 -id:A125837 - cp's OEIS frontend

A083068 7th row of number array A083064.

1, 7, 55, 439, 3511, 28087, 224695, 1797559, 14380471, 115043767, 920350135, 7362801079, 58902408631, 471219269047, 3769754152375, 30158033218999, 241264265751991, 1930114126015927, 15440913008127415, 123527304065019319, 988218432520154551, 7905747460161236407

Offset: 0

Paul Barry, Apr 21 2003

Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=10, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^(n-1)*charpoly(A,2). - Milan Janjic, Feb 21 2010

Index entries for linear recurrences with constant coefficients, signature (9,-8).

Cf. A083067, A083066, A125837.

f[n_]:=8^n; lst={}; Do[a=f[n]; Do[a-=f[m],{m,n-1,1,-1}]; AppendTo[lst,a/8],{n,1,30}]; lst (* Vladimir Joseph Stephan Orlovsky, Feb 10 2010 *)
LinearRecurrence[{9,-8},{1,7},20] (* Harvey P. Dale, Jul 18 2019 *)

a(n)=(6*8^n+1)/7 \\ Charles R Greathouse IV, Oct 07 2015

a(n) = (6*8^n+1)/7.
G.f. (1-2*x)/((1-8*x)(1-x)).
E.g.f. (6*exp(8*x)+exp(x))/7.
a(n) = 8*a(n-1)-1 with n>0, a(0)=1. - Vincenzo Librandi, Aug 08 2010
a(n) = 8^n - sum(8^i, i=0..n-1) for n>0. - Bruno Berselli, Jun 20 2013
a(n) = 1 + A125837(n+1). - Alois P. Heinz, May 20 2023

A363146 Triangle T(n,k) in which the n-th row encodes the inverse of a 3n X 3n 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).

Original entry on oeis.org

3, 7, 6, 27, 59, 48, 3, 55, 54, 219, 475, 384, 27, 443, 432, 3, 439, 438, 1755, 3803, 3072, 219, 3547, 3456, 27, 3515, 3504, 3, 3511, 3510, 14043, 30427, 24576, 1755, 28379, 27648, 219, 28123, 28032, 27, 28091, 28080, 3, 28087, 28086, 112347, 243419, 196608, 14043, 227035, 221184, 1755, 224987, 224256, 219, 224731

Offset: 1

Nei Y. Soma, May 19 2023

Each term of 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 have ascending and consecutive multiples of 3 sizes. 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 x 3m Jacobi matrices are 1 in GF(2), as proven by Sutner (1989), and alternate between -1 and 1 in R if m is odd or even, as proven by Melo (1987).
The recurrence, in line 3, uses the Iverson notation as presented in Graham, Knuth, and Patashnik (2002).
The proof of the correctness of that sequence of inverses is done by induction.

			For n = 1, the Jacobi 3 X 3 matrix has as rows
     1, 1, 0
     1, 1, 1
     0, 1, 1.
Its inverse has the rows
     0, 1, 1
     1, 1, 1
     1, 1, 0.
Representing these rows as decimal numbers the first three terms of the sequence are: 3, 7, and 6.
The next terms in the sequence occur for n = 2, given a sequence of six numbers. The Jacobi 6 X 6 matrix has as its rows:
      1, 1, 0, 0, 0, 0
      1, 1, 1, 0, 0, 0
      0, 1, 1, 1, 0, 0
      0, 0, 1, 1, 1, 0
      0, 0, 0, 1, 1, 1
      0, 0, 0, 0, 1, 1.
Its inverse has as rows:
      0, 1, 1, 0, 1, 1
      1, 1, 1, 0, 1, 1
      1, 1, 0, 0, 0, 0
      0, 0, 0, 0, 1, 1
      1, 1, 0, 1, 1, 1
      1, 1, 0, 1, 1, 0.
These 6 latter rows from binary to decimal give the next 6 terms of the sequence: 27, 49, 48, 3, 55, and 54.
Triangle T(n,k) begins:
     3,    7,    6;
    27,   59,   48,   3,   55,   54;
   219,  475,  384,  27,  443,  432,  3,  439,  438;
  1755, 3803, 3072, 219, 3547, 3456, 27, 3515, 3504, 3, 3511, 3510;
  ...

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.
K. Sutner, Linear Cellular Automata and the Garden-of-Eden, The Mathematical Intelligencer, 11(2), 1989, 49-53, p. 52.

Nei Y. Soma, Rows n = 1..30, flattened

Column k=1 gives A083713.
Column k=3 gives A083233.
T(n,3n) gives A125837(n+1).
T(n,3n-1) gives A083068.
T(n,3n-2) gives A010701.
Cf. A038184 one-dimensional cellular automaton (Rule 150) in a tape with 3n cells has as adjacency matrix the Jacobi matrices, 3n X 3n, with 1s on the lower, main and upper diagonals and the operations on it are in GF(2).

T:= n-> (M-> seq(add(abs(M[j, n*3-i])*2^i, i=0..n*3-1), j=1..n*3))
               (Matrix(n*3, (i, j)-> `if`(abs(i-j)<2, 1, 0))^(-1)):
seq(T(n), n=1..10);  # Alois P. Heinz, May 20 2023

sequence = {};
m = 6;
For[k = 1, k <= m, k++, {
  n = 3*k;
  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

row(n)=my(m=3*n, 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

The recurrence has as its base: r(1, 1) = 3; r(2, 1) = 7 and r(3, 1) = 6;
For 2 <= k <= m, and i = 1, 2, ..., 3(k-1):
    r(i, k) = 8*r(i, k-1) + r(1,1) (i != 0 (mod 3)).
And r(3k-2, k) = r(1, 1);
    r(3k-1, k) = 8*r(3(k-1), k-1) + r(2,1);
    r(3k,   k) = 8*r(3(k-1), (k-1)) + r(3, 1).

A273050 Numbers k such that ror(k) XOR rol(k) = k, where ror(x)=A038572(x) is x rotated one binary place to the right, rol(x)=A006257(x) is x rotated one binary place to the left, and XOR is the binary exclusive-or operator.

Original entry on oeis.org

0, 5, 6, 45, 54, 365, 438, 2925, 3510, 23405, 28086, 187245, 224694, 1497965, 1797558, 11983725, 14380470, 95869805, 115043766, 766958445, 920350134, 6135667565, 7362801078, 49085340525, 58902408630, 392682724205, 471219269046

Offset: 1

Alex Ratushnyak, May 13 2016

Cf. A006257, A038572, A088163, A125836 (bisection?), A125837 (bisection?).

Cf. A020988 (numbers k such that ror(k) + rol(k) = k).

ok[n_] := Block[{x = IntegerDigits[n, 2]}, x == BitXor @@@ Transpose@ {RotateLeft@ x, RotateRight@ x}]; Select[ Range[0, 10^5], ok] (* Giovanni Resta, May 14 2016 *)
ok[n_] := Block[{x = IntegerDigits[n, 2]}, x == BitXor @@@ Transpose[ {RotateLeft[x], RotateRight[x]}]]; Select[LinearRecurrence[{0, 9, 0, -8}, {0, 5, 6, 45}, 100], ok] (* Jean-François Alcover, May 22 2016, after Giovanni Resta *)

def ROR(n):                # returns A038572(n)
    BL = len(bin(n))-2
    return (n>>1) + ((n&1) << (BL-1))
def ROL(n):                # returns A006257(n) for n>0
    BL = len(bin(n))-2
    return (n*2) - (1<

Conjectures from Colin Barker, May 22 2016: (Start)
a(n) = (-11+(-1)^n+2^(-1/2+(3*n)/2)*(3-3*(-1)^n+5*sqrt(2)+5*(-1)^n*sqrt(2)))/14.
a(n) = 5*(2^(3*n/2)-1)/7 for n even.
a(n) = 3*(2^((3*n)/2-1/2)-2)/7 for n odd.
a(n) = 9*a(n-2)-8*a(n-4) for n>4.
G.f.: x^2*(5+6*x) / ((1-x)*(1+x)*(1-8*x^2)).
(End)

a(19)-a(27) from Giovanni Resta, May 14 2016

cp's OEIS Frontend

A083068 7th row of number array A083064.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A363146 Triangle T(n,k) in which the n-th row encodes the inverse of a 3n X 3n 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).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A273050 Numbers k such that ror(k) XOR rol(k) = k, where ror(x)=A038572(x) is x rotated one binary place to the right, rol(x)=A006257(x) is x rotated one binary place to the left, and XOR is the binary exclusive-or operator.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Python

Formula

Extensions