Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index
Search

Chapter 4 Notes > Section 4 > Page 909 > Note (b) Previous note-----Next note
Notes for: Systems Based on Numbers | 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.





PAGE IMAGE

Page image

RELATED LINKS

Pages related to this note:

*

All notes on this page:

* History of primes
* Finding primes
* Decimation systems
* Divisors
* Results about primes
* History of number theory
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note