|
%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
|
