cp's OEIS Frontend

A261194 Encoded square binary matrices representing an idempotent relation.

%I A261194 #24 Feb 12 2025 18:47:38
%S A261194 0,1,3,5,9,11,16,17,18,19,20,21,23,25,27,33,37,49,53,65,67,73,75,81,
%T A261194 83,89,91,141,144,145,148,149,153,154,155,157,159,181,209,217,219,272,
%U A261194 273,274,275,283,291,305,307,308,309,311,337,339,347,513,517,529
%N A261194 Encoded square binary matrices representing an idempotent relation.
%C A261194 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.
%H A261194 Philippe Beaudoin, <a href="/A261194/b261194.txt">Table of n, a(n) for n = 0..6672</a>
%e A261194 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:
%e A261194   0 1 0
%e A261194   0 1 0
%e A261194   0 1 0
%e A261194 and the 4 X 4 matrix:
%e A261194   0 1 0 0
%e A261194   0 1 0 0
%e A261194   0 1 0 0
%e A261194   0 0 0 0
%e A261194 and all larger square matrices constructed in the same way. Since 148 is in the sequence, all these matrices are idempotent.
%o A261194 (Python)
%o A261194 def getBitIndex(i, j):
%o A261194   return (i+j)*(i+j+1)//2 + j
%o A261194 def getBit(mat, i, j):
%o A261194   return (mat >> getBitIndex(i, j)) & 1
%o A261194 def setBit(mat, i, j):
%o A261194   return mat | (1 << getBitIndex(i, j))
%o A261194 def noBitLeft(mat, i, j):
%o A261194   return mat >> getBitIndex(i, j) == 0
%o A261194 def squarematrix(mat):
%o A261194   result = 0;
%o A261194   i = 0
%o A261194   while True:
%o A261194     if noBitLeft(mat, i, 0):
%o A261194       return result
%o A261194     j = 0;
%o A261194     while True:
%o A261194       if noBitLeft(mat, 0, j):
%o A261194         break
%o A261194       k = 0
%o A261194       while True:
%o A261194         if noBitLeft(mat, i, k):
%o A261194           break
%o A261194         if getBit(mat, i, k) & getBit(mat, k, j):
%o A261194           result = setBit(result, i, j)
%o A261194           break
%o A261194         k += 1
%o A261194       j += 1
%o A261194     i += 1
%o A261194   return result
%o A261194 index = 0
%o A261194 mat = 0
%o A261194 while True:
%o A261194   if mat == squarematrix(mat):
%o A261194     print(index, mat)
%o A261194     index += 1
%o A261194   mat += 1
%Y A261194 Cf. A121337, A231428, A261195.
%K A261194 nonn
%O A261194 0,3
%A A261194 _Philippe Beaudoin_, Aug 11 2015