Where the Automaton Starts Repeating
A ring of n cells runs the rule-table automaton of #2141: three values read
as left centre right give a position from 0 to 7, the bit of rule at that
position is the cell's next value, the ring wraps, and all cells change
simultaneously.
Call the starting row generation 0. Print two integers:
s the smallest index such that generation s occurs again later
p the smallest positive number with generation s + p equal to generation s
So s is where the repeating part begins and p is how long it is. The
generations before s happen once and never come back.
``` n = 4, rule = 90, row = 0100 -> 2 1
gen 0 0100 gen 1 1010 gen 2 0000 gen 3 0000 equal to generation 2, so s = 2 and p = 1 ```
``` n = 5, rule = 150, row = 00100 -> 0 3
the starting row itself comes back after three generations, so nothing happens only once and s is 0 ```
## Why it always terminates
A generation is a row of n cells, each 0 or 1, so there are exactly
2^n possible generations and no more. Generations 0 through 2^n are
2^n + 1 rows drawn from a set of size 2^n, so by the pigeonhole principle
two of them are equal. The automaton is also DETERMINISTIC: the next generation
is a function of the current one alone, with no memory of how it was reached.
So once a row repeats, everything after it repeats too, forever, and the answer
exists for every input. With n at its limit of 16 that bound is 65537
generations, which is why simulating to the repeat is affordable at all.
## What most people try first
Running a fixed number of generations, say a few thousand, and looking for two
equal rows among them. That is both unsound and slower than it needs to be: the
tail before the cycle can be long, and comparing every new row against every
stored row costs O(n) per comparison and O(k^2) comparisons after k
generations, which at 65537 generations is far too much work.
## Each row is one integer
With n at most 16, a row fits in 16 bits, so a whole generation is a number
below 65536. That turns "have I seen this row before" into one array lookup:
first = array of 2^n entries, all -1
m = the starting row packed into bits
gen = 0
while first[m] == -1:
first[m] = gen
m = step(m)
gen = gen + 1
print first[m], gen - first[m]
When the loop stops, m is the first row that has been met twice. first[m] is
the generation it appeared in originally and gen is the generation it has just
reappeared in, so the difference is the period.
## Why that is the SMALLEST s, and the smallest p
Two claims, and both need the argument rather than the assertion.
For s: the loop stops at the first repeat it ever meets, so no generation
with index below first[m] recurs. Suppose one did, say generation j with
j < first[m] equals some generation k with k > j. Then the loop would have
stopped at step k, and k < gen because gen is where it actually stopped,
so first[m] would have been at most j, a contradiction. So first[m] is the
smallest index that recurs.
For p: because the step is a function, generation s + i is determined by
generation s for every i, so the sequence from s onwards is purely
periodic with period gen - s. Any smaller positive q with generation
s + q equal to generation s would mean row m reappears at index s + q,
and s + q < gen would have stopped the loop earlier. So gen - s is minimal.
## The boundary that breaks a careless implementation
p is at least 1, never 0, because s + p must come strictly after s. A row
that is already stable, such as anything under rule 0 after it empties, gives
p = 1 rather than p = 0. Rings of one and two cells are legal, and the wrap
makes a cell its own neighbour there, exactly as in #2141.
## Cost
At most 2^n + 1 generations, each O(n), so O(n 2^n) time and O(2^n)
memory for the seen array. At n = 16 that is about a million cell updates and
65536 array entries.