A007495 Josephus problem: survivors.

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

Author

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

Keywords

• easy
• nonn

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

Examples

			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)
		

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

Crossrefs

Cf. A032434, A054995.

Programs

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 *)

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

Extensions

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