2147. The Population After a Billion Billion Generations

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.

Print how many cells are alive after exactly g generations. Generation 0 is the starting row, so if g is 0 the answer is the starting population.

The catch is the size of g. It reaches 10^18, and n is at most 16, so stepping the automaton g times is not an option and never will be: at a billion generations a second it would take about thirty years.

n = 5, rule = 90, g = 0, row = 00100 -> 1 n = 5, rule = 90, g = 7, row = 00100 -> 2 n = 16, rule = 204, g = 10^18, row = 1011001011010110 -> 9

The last one is answerable by hand. Rule 204 has bits set exactly at the four positions whose centre value is 1, so the rule copies the centre and nothing ever changes. The population is the starting population, 9, for every g.

## What most people try first

A loop that runs g generations. It is correct and it cannot finish. The second attempt is usually to look for a formula in n, rule and g, which does not exist: the rule table is arbitrary and the behaviour across the 256 rules has no closed form.

## The state space is tiny, which is the whole opening

A generation is n bits with n at most 16, so there are at most 65536 possible rows. The step is a function of the current row alone. So among generations 0, 1, ..., 65536 two must be equal by the pigeonhole principle, and once a row repeats everything after it repeats, forever. The sequence of generations is a TAIL of rows that happen once, followed by a LOOP that goes round for ever:

gen: 0 1 2 ... s-1 | s s+1 ... s+p-1 | s s+1 ... [----- the tail ----] [-- the loop, length p --] [ again ...

So instead of g steps, take at most 65537 of them and record where each row first appeared. That gives s and p, exactly as in #2143. Then:

if g < s: the answer is generation g, which is in the tail, already recorded otherwise: generation g equals generation s + ((g - s) mod p)

Count the set bits of that row.

## Why the reduction is correct

Write step for the function taking one generation to the next, so generation k is step applied k times to generation 0. The loop found above means generation s + p equals generation s. Applying step to both sides i times gives generation s + p + i equals generation s + i for every i at least 0, since step is a function and equal inputs give equal outputs. By induction on j, generation s + i + j p equals generation s + i for every j at least 0.

Now take any g at least s. Write g - s = q p + m with 0 <= m < p, which is division with remainder. Then g = s + m + q p, so generation g equals generation s + m, and s + m is below s + p, which is a row already recorded. For g below s the row was recorded directly. So every g is answered from the recorded prefix, and the prefix has at most 65537 entries.

## Overflow, and the one language that needs care

g reaches 10^18, which is far past the signed 32 bit limit of 2147483647, so it must be read into a 64 bit type. Signed 64 bit reaches about 9.2 * 10^18, so 10^18 fits with room to spare, and no intermediate value grows: (g - s) mod p is computed directly from values already in range.

JavaScript is the exception. A plain Number is exact only below 2^53, which is about 9.007 * 10^15, so 10^18 read as a Number is NOT the value in the input, and (g - s) % p on it gives a silently wrong remainder. Read g as a BigInt, do the subtraction and the remainder in BigInt, and only then convert the result, which is below p and so below 65537, back to a Number for use as an index. Note also that the row masks are at most 16 bits, so the bitwise operators used on THEM are exact and need no BigInt.

## Cost

At most 2^n + 1 steps of O(n) each to find the tail and the loop, so O(n 2^n) time and O(2^n) memory, independent of g. At n = 16 that is about a million cell updates whether g is 7 or 10^18.

Constraints - `1 ≤ n ≤ 16` - `0 ≤ rule ≤ 255` - `0 ≤ g ≤ 10^18` - every character of generation 0 is `0` or `1` - the row is a ring and all cells change simultaneously, from the previous generation only - `g` exceeds the signed 32 bit range and also exceeds `2^53`, so JavaScript needs BigInt for it