A118141 - OEIS

%I #14 Mar 08 2015 18:40:13

%S 2,3,5,4,23,8,11,27,29,30,47,62,17,339,23,254,167,512,59,2339,185,

%T 2046,95,1024,125,2043,35,3276,2039,340,47,4091,509,4094,335,3590,

%U 1025,16379,119,1048574,4679,16382,371,92819,12281,8388606,191,2097152,6149,262139

%N Length of the longest perfect parity pattern with n columns.

%C Also the length of the unique perfect parity pattern whose first row is 0....01 (with n-1 zeros).

%C Definitions: A parity pattern is a matrix of 0's and 1's with the property that every 0 is adjacent to an even number of 1's and every 1 is adjacent to an odd number of 1's.

%C It is called perfect if no row or column is entirely zero. Every parity pattern can be built up in a straightforward way from the smallest perfect subpattern in its upper left corner.

%C For example, the 3 X 2 matrix

%C 11

%C 00

%C 11

%C is a parity pattern built up from the perfect 1 X 2 pattern "11". The 3 X 5 matrix

%C 01010

%C 11011

%C 01010

%C is similarly built up from the perfect 3 X 2 pattern of its first two columns. The 4 X 4 matrix

%C 0011

%C 0100

%C 1101

%C 0101

%C is perfect. So is the 5 X 5

%C 01110

%C 10101

%C 11011

%C 10101

%C 01110

%C which moreover has 8-fold symmetry (cf. A118143).

%C All perfect parity patterns of n columns can be shown to have length d-1 where d divides a(n)+1.

%D D. E. Knuth, The Art of Computer Programming, Section 7.1.3.

%H Andries E. Brouwer, Jun 15 2008, <a href="/A118141/b118141.txt">Table of n, a(n) for n = 1..85</a>

%H Andries E. Brouwer, <a href="http://www.win.tue.nl/~aeb/ca/madness/madrect.html">Button Madness and Lights Out on rectangles</a>

%Y The number of perfect parity patterns that have exactly n columns is A000740.

%Y The sequence of all n such that an n X n parity pattern exists is A117870 (cf. A076436, A093614, A094425).

%Y Cf. also A118142, A118143.

%Y Cf. A007802.

%K nonn

%O 1,1

%A _Don Knuth_, May 11 2006

%E More terms from _John W. Layman_, May 17 2006

%E More terms from _Andries E. Brouwer_, Jun 15 2008