OFFSET
0,3
COMMENTS
We encode an n X n binary matrix reading it antidiagonal by antidiagonal, starting from the least significant bit. A given entry in the sequence therefore represents the infinite family of n X n matrices that can be obtained by adding zero antidiagonals. All of these matrices represent idempotent relations. This encoding makes it possible to obtain a sequence rather than a table.
LINKS
Philippe Beaudoin, Table of n, a(n) for n = 0..6672
EXAMPLE
For example, 148 = 0b10010100 encodes all square matrices with the first four antidiagonals equal to ((0), (0, 1), (0, 1, 0), (0, 1, 0, 0)). For example the 3 X 3 matrix:
0 1 0
0 1 0
0 1 0
and the 4 X 4 matrix:
0 1 0 0
0 1 0 0
0 1 0 0
0 0 0 0
and all larger square matrices constructed in the same way. Since 148 is in the sequence, all these matrices are idempotent.
PROG
(Python)
def getBitIndex(i, j):
return (i+j)*(i+j+1)//2 + j
def getBit(mat, i, j):
return (mat >> getBitIndex(i, j)) & 1
def setBit(mat, i, j):
return mat | (1 << getBitIndex(i, j))
def noBitLeft(mat, i, j):
return mat >> getBitIndex(i, j) == 0
def squarematrix(mat):
result = 0;
i = 0
while True:
if noBitLeft(mat, i, 0):
return result
j = 0;
while True:
if noBitLeft(mat, 0, j):
break
k = 0
while True:
if noBitLeft(mat, i, k):
break
if getBit(mat, i, k) & getBit(mat, k, j):
result = setBit(result, i, j)
break
k += 1
j += 1
i += 1
return result
index = 0
mat = 0
while True:
if mat == squarematrix(mat):
print(index, mat)
index += 1
mat += 1
CROSSREFS
KEYWORD
nonn
AUTHOR
Philippe Beaudoin, Aug 11 2015
STATUS
approved