A007495 Josephus problem: survivors. (Formerly M0237)

1, 1, 2, 2, 2, 4, 5, 4, 8, 8, 7, 11, 8, 13, 4, 11, 12, 8, 12, 2, 13, 7, 22, 2, 8, 13, 26, 4, 26, 29, 17, 27, 26, 7, 33, 20, 16, 22, 29, 4, 13, 22, 25, 14, 22, 37, 18, 46, 42, 46, 9, 41, 12, 7, 26, 42, 24, 5, 44, 53, 52, 58, 29, 22, 12, 48, 27, 30, 58, 52, 49, 57, 13, 14, 32, 24, 75, 8, 67

Offset

1,3

Comments

If, in a circle of k persons, every n-th person is removed, the survivor is t(k,n) + 1. So the recurrence generates a sequence of survivors. See the formula. For more details see the "Proof of the formula". - Gerhard Kirchner, Oct 23 2016

The recurrence formula looks like a simple congruential generator for pseudo-random numbers. Is a(n) pseudo-random? It seems so, see: "Stochastic aspects". I used the formula for extending a(n) up to n=2^20. - Gerhard Kirchner, Nov 10 2016

References

Friend H. Kierstead, Jr., Computer Challenge Corner, J. Rec. Math., 10 (1977), see p. 124.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Seiichi Manyama, Table of n, a(n) for n = 1..5000 (first 1000 terms from T. D. Noe)

Gerhard Kirchner, Proof of the formula.

Gerhard Kirchner, Stochastic aspects.

Eric Weisstein's World of Mathematics, Josephus Problem.

Robert G. Wilson v, Notes, n.d..

Index entries for sequences related to the Josephus Problem

Formula

Let t(k,n) = (t(k-1,n) + n) mod k and t(1,n) = 0; then a(n) = t(n,n) + 1. - Gerhard Kirchner, Oct 23 2016

Example

From Gerhard Kirchner, Oct 23 2016: (Start)
If n = 4 we have that:
  t(1,4) = 0.
  t(2,4) = (0+4) mod 2 = 0.
  t(3,4) = (0+4) mod 3 = 1.
  t(4,4) = (1+4) mod 4 = 1.
So a(4) = 1 + 1 = 2. (End)

Mathematica

(* First do *) Needs["Combinatorica`"] (* then *) f[n_] := Last@ InversePermutation@ Josephus[n, n]; Array[f, 80] (* Robert G. Wilson v, Jul 31 2010 *)
t[k_, n_] := t[k, n] = Mod[t[k-1, n]+n, k]; t[1, _] = 0; a[n_] := t[n, n]+1; Array[a, 1000] (* Jean-François Alcover, Oct 23 2016, after Gerhard Kirchner *)

Crossrefs

Cf. A032434, A054995.

Sequence in context: A024681 A240327 A308771 * A122385 A035002 A032578

Adjacent sequences: A007492 A007493 A007494 * A007496 A007497 A007498

Keyword

easy,nonn

Author

N. J. A. Sloane, Robert G. Wilson v

Extensions

More terms from Robert G. Wilson v, Jul 31 2010

Status

approved