

A118141


Length of the longest perfect parity pattern with n columns.


6



2, 3, 5, 4, 23, 8, 11, 27, 29, 30, 47, 62, 17, 339, 23, 254, 167, 512, 59, 2339, 185, 2046, 95, 1024, 125, 2043, 35, 3276, 2039, 340, 47, 4091, 509, 4094, 335, 3590, 1025, 16379, 119, 1048574, 4679, 16382, 371, 92819, 12281, 8388606, 191, 2097152, 6149, 262139
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Also the length of the unique perfect parity pattern whose first row is 0....01 (with n1 zeros).
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.
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.
For example, the 3 X 2 matrix
11
00
11
is a parity pattern built up from the perfect 1 X 2 pattern "11". The 3 X 5 matrix
01010
11011
01010
is similarly built up from the perfect 3 X 2 pattern of its first two columns. The 4 X 4 matrix
0011
0100
1101
0101
is perfect. So is the 5 X 5
01110
10101
11011
10101
01110
which moreover has 8fold symmetry (cf. A118143).
All perfect parity patterns of n columns can be shown to have length d1 where d divides a(n)+1.


REFERENCES

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


LINKS

Andries E. Brouwer, Jun 15 2008, Table of n, a(n) for n = 1..85
Andries E. Brouwer, Button Madness and Lights Out on rectangles


CROSSREFS

The number of perfect parity patterns that have exactly n columns is A000740.
The sequence of all n such that an n X n parity pattern exists is A117870 (cf. A076436, A093614, A094425).
Cf. also A118142, A118143.
Cf. A007802.
Sequence in context: A139537 A111631 A235610 * A175210 A264047 A264035
Adjacent sequences: A118138 A118139 A118140 * A118142 A118143 A118144


KEYWORD

nonn


AUTHOR

Don Knuth, May 11 2006


EXTENSIONS

More terms from John W. Layman, May 17 2006
More terms from Andries E. Brouwer, Jun 15 2008


STATUS

approved



