Longest non-repeating Game-of-Life sequence Given a positive integer N,
determine the starting pattern on a N x N-grid that yield
the longest non-repeating sequence under Game of Life-rules, and ends 
with a fixed pattern (cycle of length 1), played on a torus.

The goal is not the shortest program, but the quickest.

Since the world is finite, you will eventually end up in a loop,
thus repeating an already visited state. If this loop has period 1, then the starting pattern is a valid candidate.

Output: Starting pattern and total number of unique states in the sequence (including starting pattern).

Now, the 1x1-torus is special, since a cell may be considered neighbouring to itself or not, but in practice, there is no problem, a single living cell will in either case just die (of overcrowding or loneliness). 
Thus, input 1 yields a sequence of length 2, the sequence being one cell living, then forever dead.

The motivation for this question is that is an analogue of the busy beaver function, but definitely less complex, since we have a bound on memory. This will be a nice sequence to include on OEIS, as well.

For N=3, the sequence length is 3, any pattern on the left hand side reaches a completely black 3x3-square, and then dies. (All patterns that are part of 1-cycle removed).
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);
    }
  }
}