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 kth 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.



Image Source Notebooks:

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