Longest non-repeating Game-of-Life sequence
C++ up to N=6

3x3 answer 3: 111 000 000                                                                                        
4x4 answer 10: 1110 0010 1100 0000                                                                               
5x5 answer 52: 11010 10000 11011 10100 00000                                                                     
6x6 answer 91: 100011 010100 110011 110100 101000 100000                                                         


This technique is centered around a fast next state function.  Each board is represented as a bitmask of N^2 bits, and bit-twiddly tricks are used to compute the next state for all cells at once.  next compiles down to about 200 100 assembly instructions for N &lt;= 8.  Then we just do the standard try-all-states-until-they-repeat and pick the longest one.

Takes a few seconds up to 5x5, a few hours for 6x6.

#include &lt;stdint.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;algorithm&gt;
using namespace std;

#define N 6

typedef uint64_t board;

// board is N bits by N bits, with indexes like this (N=4):                                                        
//  0  1  2  3                                                                                                     
//  4  5  6  7                                                                                                     
//  8  9 10 11                                                                                                     
// 12 13 14 15                                                                                                     

#if N==3
#define LEFT_COL (1 + (1&lt;&lt;3) + (1&lt;&lt;6))
#define RIGHT_COL ((1&lt;&lt;2) + (1&lt;&lt;5) + (1&lt;&lt;8))
#define ALL 0x1ffULL
#elif N==4
#define LEFT_COL 0x1111ULL
#define RIGHT_COL 0x8888ULL
#define ALL 0xffffULL
#elif N==5
#define LEFT_COL (1ULL + (1&lt;&lt;5) + (1&lt;&lt;10) + (1&lt;&lt;15) + (1&lt;&lt;20))
#define RIGHT_COL ((1ULL&lt;&lt;4) + (1&lt;&lt;9) + (1&lt;&lt;14) + (1&lt;&lt;19) + (1&lt;&lt;24))
#define ALL 0x1ffffffULL
#elif N==6
#define LEFT_COL (1 + (1&lt;&lt;6) + (1&lt;&lt;12) + (1&lt;&lt;18) + (1&lt;&lt;24) + (1ULL&lt;&lt;30))
#define RIGHT_COL ((1&lt;&lt;5) + (1&lt;&lt;11) + (1&lt;&lt;17) + (1&lt;&lt;23) + (1&lt;&lt;29) + (1ULL&lt;&lt;35))
#define ALL 0xfffffffffULL
#else
#error "bad N"
#endif

static inline board north(board b) {
  return (b &gt;&gt; N) + (b &lt;&lt; N*N-N);
}
static inline board south(board b) {
  return (b &lt;&lt; N) + (b &gt;&gt; N*N-N);
}
static inline board west(board b) {
  return ((b &amp; ~LEFT_COL) &gt;&gt; 1) + ((b &amp; LEFT_COL) &lt;&lt; N-1);
}
static inline board east(board b) {
  return ((b &amp; ~RIGHT_COL) &lt;&lt; 1) + ((b &amp; RIGHT_COL) &gt;&gt; N-1);
}

board next(board b) {
  board n1 = north(b);
  board n2 = south(b);
  board n3 = west(b);
  board n4 = east(b);
  board n5 = north(n3);
  board n6 = north(n4);
  board n7 = south(n3);
  board n8 = south(n4);

  // add all the bits bitparallel-y to a 2-bit accumulator with overflow
  board a0 = 0;
  board a1 = 0;
  board overflow = 0;
#define ADD(x) overflow |= a0 &amp; a1 &amp; x; a1 ^= a0 &amp; x; a0 ^= x;

  a0 = n1; // no carry yet
  a1 ^= a0 &amp; n2; a0 ^= n2; // no overflow yet
  a1 ^= a0 &amp; n3; a0 ^= n3; // no overflow yet
  ADD(n4);
  ADD(n5);
  ADD(n6);
  ADD(n7);
  ADD(n8);
  return (a1 &amp; (b | a0)) &amp; ~overflow &amp; ALL;
}
void print(board b) {
  for (int i = 0; i &lt; N; i++) {
    for (int j = 0; j &lt; N; j++) {
      printf("%d", (int)(b &gt;&gt; i*N+j &amp; 1));
    }
    printf(" ");
  }
  if (b &gt;&gt; N*N) printf("*");
  printf("\n");
}

int main(int argc, char *argv[]) {
  // Somewhere in the starting pattern there are a 1 and 0 together.  Using translational                          
  // and rotational symmetry, we can put these in the first two bits.  So we need only consider                    
  // 1 mod 4 boards.                                                                                               

  board steps[10000];
  int maxsteps = -1;
  for (board b = 1; b &lt; 1ULL &lt;&lt; N*N; b += 4) {
    int nsteps = 0;
    board x = b;
    while (true) {
      int repeat = steps + nsteps - find(steps, steps + nsteps, x);
      if (repeat &gt; 0) {
        if (repeat == 1 &amp;&amp; nsteps &gt; maxsteps) {
          printf("%d: ", nsteps);
          print(b);
          maxsteps = nsteps;
        }
        break;
      }
      steps[nsteps++] = x;
      x = next(x);
    }
  }
}