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..
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
KEYWORD
easy,nonn
AUTHOR
EXTENSIONS
More terms from Robert G. Wilson v, Jul 31 2010
STATUS
approved