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