A118141 Length of the longest perfect parity pattern with n columns.

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

Offset: 1

Author

Don Knuth, May 11 2006

Keywords

• nonn

Comments

Also the length of the unique perfect parity pattern whose first row is 0....01 (with n-1 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 8-fold symmetry (cf. A118143).

All perfect parity patterns of n columns can be shown to have length d-1 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.

Extensions

More terms from John W. Layman, May 17 2006

More terms from Andries E. Brouwer, Jun 15 2008