A261194 Encoded square binary matrices representing an idempotent relation.

0, 1, 3, 5, 9, 11, 16, 17, 18, 19, 20, 21, 23, 25, 27, 33, 37, 49, 53, 65, 67, 73, 75, 81, 83, 89, 91, 141, 144, 145, 148, 149, 153, 154, 155, 157, 159, 181, 209, 217, 219, 272, 273, 274, 275, 283, 291, 305, 307, 308, 309, 311, 337, 339, 347, 513, 517, 529

Offset: 0

Author

Philippe Beaudoin, Aug 11 2015

Keywords

• nonn

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.

Examples

			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.
		

Links

• Philippe Beaudoin, Table of n, a(n) for n = 0..6672

Crossrefs

Cf. A121337, A231428, A261195.

Programs

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