A384209 Maximum period for Game of Life on a simple graph with n vertices.

1, 1, 1, 1, 2, 4, 8, 14, 27

Offset

1,5

Comments

The usual rules of Game of Life apply: A live vertex lives on to the next generation only if it has 2 or 3 living neighbors. A dead vertex comes alive if it has exactly 3 living neighbors.

Links

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

Pontus von Brömssen, Illustration for n=6.

Pontus von Brömssen, Illustration for n=7.

Pontus von Brömssen, Illustration for n=8.

Eric Weisstein's World of Mathematics, Game of Life.

Wikipedia, Conway's Game of Life.

Example

For n <= 4, no graph with n vertices has a pattern with period greater than 1, so a(n) = 1.
For 5 <= n <= 9, there is a unique graph on n vertices that admits a pattern with the maximum period a(n), as detailed in the table below.
  n | a(n) | optimal graph in graph6 format
  --+------+-------------------------------
  5 |   2  | "D]{" (wheel)
  6 |   4  | "E]yw" (complement of the disjoint union of two paths on 3 vertices each)
  7 |   8  | "FE~vw" (complement of the disjoint union of K_1, K_2, and the paw graph)
  8 |  14  | "GEnvZ{" (complement of a triangle with "tentacles" of lengths 1, 2, and 2)
  9 |  27  | "HCZJtzm"

Crossrefs

Cf. A357951.

Sequence in context: A164166 A164161 A068011 * A048238 A048140 A179817

Adjacent sequences: A384206 A384207 A384208 * A384210 A384211 A384212

Keyword

nonn,more

Author

Pontus von Brömssen, May 22 2025

Status

approved