A094425 -id:A094425 - cp's OEIS frontend

A093614 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind.

5, 6, 10, 12, 15, 17, 18, 20, 24, 25, 30, 31, 33, 34, 35, 36, 40, 42, 45, 48, 50, 51, 54, 55, 60, 62, 63, 65, 66, 68, 70, 72, 75, 78, 80, 84, 85, 90, 93, 95, 96, 99, 100, 102, 105, 108, 110, 114, 115, 119, 120, 124, 125, 126, 127, 129, 130, 132, 135, 136, 138

Offset: 1

Ralf Stephan, May 22 2004

nonn

Goldwasser et al. proved that 2^k+-1 belongs to the set, for k>4.

Closed under multiplication by positive integers. - Don Knuth, May 11 2006

Ralf Stephan and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms 1 through 61 were computed by Ralf Stephan, May 22 2004; terms 62 through 1000 by Thomas Buchholz, May 16 2014]
M. Hunziker, A. Machiavelo and J. Park, Chebyshev polynomials over finite fields and reversibility of sigma-automata on square grids, Theoretical Comp. Sci., 320 (2004), 465-483.
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11 (No. 2, 1989), 49-53.
K. Sutner, The computational complexity of cellular automata, in Lect. Notes Computer Sci., 380 (1989), 451-459.
Eric Weisstein's World of Mathematics, Lights-Out Puzzle

Equals A117870(n) + 1.

Cf. A094425 (primitive elements), A076436.

{ F2(n)=local(t, t1, t2, tmp); t1=Mod(0, 2); t2=Mod(1, 2); t=Mod(1, 2)*x; for(k=2, n, tmp=t*t2-t1; t1=t2; t2=tmp); tmp }
for(n=2, 200, t=F2(n); if(gcd(t, subst(t, x, 1-x))!=1, print1(n", ")))

More terms from Thomas Buchholz, May 16 2014

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

Original entry on oeis.org

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

Don Knuth, May 11 2006

nonn

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.

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

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

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.

More terms from John W. Layman, May 17 2006

More terms from Andries E. Brouwer, Jun 15 2008

cp's OEIS Frontend

A093614 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions