login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A075462 a(n) is the number of solutions to the all-ones lights out problem on an n X n square. 12
1, 1, 1, 16, 4, 1, 1, 1, 256, 1, 64, 1, 1, 16, 1, 256, 4, 1, 65536, 1, 1, 1, 16384, 16, 1, 1, 1, 1, 1024, 1048576, 1, 1048576, 65536, 16, 64, 1, 1, 1, 4294967296, 1, 4, 1, 1, 16, 1, 1, 1073741824, 1, 256, 256, 1, 1, 4, 16, 1, 1, 1, 1, 4194304, 1, 1099511627776, 16777216 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

In these counts, nonidentical reflected and rotated solutions are considered distinct.

REFERENCES

Caro, Y., Simple proofs to three parity theorems, Ars Combin. 42 (1996), 175-180.

Conlon, M. M.; Falidas, M.; Forde, M. J.; Kennedy, J. W.; McIlwaine, S.; and Stern, J., Inversion numbers of graphs, Graph Theory Notes New York 37 (1999), 42-48.

Cowen, R.; Hechler, S. H.; Kennedy, J. W.; and Ryba, A., Inversion and neighborhood inversion in graphs, Graph Theory Notes New York 37 (1999), 37-41.

Cowen, R. and Kennedy, J., The Lights Out puzzle, Math. Educ. Res. 9 (2000), 28-32.

Goldwasser, J. and Klostermeyer, W., Maximization versions of 'Lights Out' games in grids and graphs, Congr. Numer. 126 (1997), 99-111.

K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), 49-53.

LINKS

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms were extended by Max Alekseyev, Sep 17 2009; terms 63 through 1000 were computed by Thomas Buchholz, May 16 2014]

Millstone Website, Lights Out

Eric Weisstein's World of Mathematics, Lights Out Puzzle

Whitman College Department of Mathematics, Lights Out

FORMULA

a(n) = 2^A159257(n) [From Max Alekseyev, Sep 17 2009]

MATHEMATICA

m[k_] := SparseArray[ {Band[{1, 1}] -> 1, Band[{1, 2}] -> 1, Band[{2, 1}] -> 1}, {k, k}]; b[k_, 0] := SparseArray[ Band[{1, 1}] -> 1, {k, k}]; b[k_, 1] := m[k]; b[k_, n_] := b[k, n] = Mod[m[k].b[k, n-1] + b[k, n-2], 2]; A159257[n_] := First[ Dimensions[ NullSpace[b[n, n], Modulus -> 2]]]; A159257[1] = 0; a[n_] := 2^A159257[n]; Table[a[n], {n, 1, 62}] (* Jean-Fran├žois Alcover, Oct 10 2012, after Max Alekseyev and Birkas Gyorgy *)

CROSSREFS

Cf. A075463, A075464, A076436, A076437.

Sequence in context: A070569 A084473 A040246 * A082959 A232014 A018814

Adjacent sequences:  A075459 A075460 A075461 * A075463 A075464 A075465

KEYWORD

nonn,nice

AUTHOR

Eric W. Weisstein, Sep 17, 2002

EXTENSIONS

More terms from Max Alekseyev, Sep 17 2009, and Thomas Buchholz, May 16 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 24 06:31 EDT 2014. Contains 248502 sequences.