Notes

Chapter 4: Systems Based on Numbers

Section 4: The Sequence of Primes


Decimation systems

A somewhat similar system starts with a line of cells, then at each step removes every k^th cell that remains, as in the pictures below. The number of steps for which a cell at position n will survive can be computed as

Module[{q=n+k-1,s=1},While[Mod[q,k]!=0, q=Ceiling[(k-1)q/k];s++];s]

If a cell is going to survive for s steps, then it turns out that this can be determined by looking at the last s digits in the base k representation of its position. For k=2, a cell survives for s steps if these digits are all 0 (so that s==IntegerExponent[n, k]). But for k>2, no such simple characterization appears to exist.

If the cells are arranged on a circle of size n, the question of which cell is removed last is the so-called Josephus problem. The solution is Fold[Mod[#1+k,#2,1]&,0,Range[n]], or FromDigits[RotateLeft[IntegerDigits[n,2]],2] for k=2.

From Stephen Wolfram: A New Kind of Science [citation]