A095905 Sequence generated from Golomb's proof of de Bruijn's theorem on a torus considered as a matrix.

1, 21, 333, 5373, 86589, 1395549, 22491837, 362497437, 5842314621, 94159673181, 1517556760893, 24458225530653, 394189404655869, 6353089129389789, 102391746224652477, 1650231797698803357, 26596528397525794941

Offset

1,2

Comments

Solomon W. Golomb's proof of de Bruijn's coloring theorem on a chessboard for 1 X 4 size pieces (that its impossible to color a 6 X 6 chessboard with pieces of size 1 X 4), is generalized for the torus by using M in a chessboard format. To quote Watkins, (p. 228): "However, Golomb was able to come up with a new coloring that, for example, shows that even on a torus you can't cover an m X n chessboard with 1 X 4 pieces unless 4 divides either m or n-that is, de Bruijn's theorem still holds, at least for 1 X 4 pieces." [p. 229]: And, "By the way, as de Bruijn himself originally proved, I should mention that de Bruijn's theorem holds in all higher dimensions; and so for example, an a X b X c solid block can be constructed out of 1 X 1 X k bricks only when k divides at least one of a,b, or c.".

References

John J. Watkins, "Across the Board, the Mathematics of Chessboard Problems", Princeton University Press, 2004, p. 227-229.

Links

Table of n, a(n) for n=1..17.

Index entries for linear recurrences with constant coefficients, signature (15,18).

Formula

a(1) = 1, a(2) = 21, a(n+2) = 15*a(n+1) + 18*a(n), n>2. Matrix method: Let M = the 6 X 6 matrix [1 2 1 2 1 2 / 3 4 3 4 3 4 / 1 2 1 2 1 2 / 3 4 3 4 3 4 / 1 2 1 2 1 2 / 3 4 3 4 3 4]. Then M^n *[1 0 0 0 0 0] = [a(n) q a(n) q a(n) q a(n) q], where q = a term in another sequence with the same recursion rule.

G.f.: -x*(6*x+1) / (18*x^2+15*x-1). [Colin Barker, Dec 06 2012]

Example

a(3) = 333 = 14*21 + 18
a(3) = 333 since M^3 * [1 0 0 0 0 0] = [333 729 333 729 333 729].

Mathematica

a[n_] := (MatrixPower[{{1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}, {1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}, {1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}}, n].{{1}, {0}, {0}, {0}, {0}, {0}})[[1, 1]]; Table[ a[n], {n, 17}] (* Robert G. Wilson v, Jun 16 2004 *)
LinearRecurrence[{15, 18}, {1, 21}, 30] (* Harvey P. Dale, Apr 07 2017 *)

Crossrefs

Sequence in context: A322540 A016191 A297336 * A051525 A107396 A036224

Adjacent sequences: A095902 A095903 A095904 * A095906 A095907 A095908

Keyword

nonn,easy

Author

Gary W. Adamson, Jun 13 2004

Extensions

Edited, corrected and extended by Robert G. Wilson v, Jun 16 2004

Status

approved