Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #26 Mar 05 2022 20:08:57
%S 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,
%T 1,1,1024,1048576,1,1048576,65536,16,64,1,1,1,4294967296,1,4,1,1,16,1,
%U 1,1073741824,1,256,256,1,1,4,16,1,1,1,1,4194304,1,1099511627776,16777216
%N a(n) is the number of solutions to the all-ones lights out problem on an n X n square.
%C In these counts, nonidentical reflected and rotated solutions are considered distinct.
%D Caro, Y., Simple proofs to three parity theorems, Ars Combin. 42 (1996), 175-180.
%D 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.
%D 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.
%D Cowen, R. and Kennedy, J., The Lights Out puzzle, Math. Educ. Res. 9 (2000), 28-32.
%D Goldwasser, J. and Klostermeyer, W., Maximization versions of 'Lights Out' games in grids and graphs, Congr. Numer. 126 (1997), 99-111.
%D K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), 49-53.
%H Max Alekseyev and Thomas Buchholz, <a href="/A075462/b075462.txt">Table of n, a(n) for n = 1..1000</a> [terms were extended by Max Alekseyev, Sep 17 2009; terms 63 through 1000 were computed by Thomas Buchholz, May 16 2014]
%H Millstone Website, <a href="http://www.millstone.demon.co.uk/games/lightsout/start.htm">Lights Out</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LightsOutPuzzle.html">Lights Out Puzzle</a>
%H Whitman College Department of Mathematics, <a href="http://www.whitman.edu/offices_departments/mathematics/lights_out/">Lights Out</a>
%F a(n) = 2^A159257(n). - _Max Alekseyev_, Sep 17 2009
%t 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_ *)
%Y Cf. A075463, A075464, A076436, A076437.
%K nonn,nice
%O 1,4
%A _Eric W. Weisstein_, Sep 17 2002
%E More terms from _Max Alekseyev_, Sep 17 2009, and _Thomas Buchholz_, May 16 2014