%I M0237 #69 Oct 29 2023 21:23:11
%S 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,
%T 29,17,27,26,7,33,20,16,22,29,4,13,22,25,14,22,37,18,46,42,46,9,41,12,
%U 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
%N Josephus problem: survivors.
%C 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
%C 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
%D Friend H. Kierstead, Jr., Computer Challenge Corner, J. Rec. Math., 10 (1977), see p. 124.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Seiichi Manyama, <a href="/A007495/b007495.txt">Table of n, a(n) for n = 1..5000</a> (first 1000 terms from T. D. Noe)
%H Gerhard Kirchner, <a href="/A007495/a007495_2.txt">Proof of the formula</a>.
%H Gerhard Kirchner, <a href="/A007495/a007495.pdf">Stochastic aspects</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>.
%H Robert G. Wilson v, <a href="/A007495/a007495_1.pdf">Notes, n.d.</a>.
%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F 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
%e From _Gerhard Kirchner_, Oct 23 2016: (Start)
%e If n = 4 we have that:
%e t(1,4) = 0.
%e t(2,4) = (0+4) mod 2 = 0.
%e t(3,4) = (0+4) mod 3 = 1.
%e t(4,4) = (1+4) mod 4 = 1.
%e So a(4) = 1 + 1 = 2. (End)
%t (* First do *) Needs["Combinatorica`"] (* then *) f[n_] := Last@ InversePermutation@ Josephus[n, n]; Array[f, 80] (* _Robert G. Wilson v_, Jul 31 2010 *)
%t 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_ *)
%Y Cf. A032434, A054995.
%K easy,nonn
%O 1,3
%A _N. J. A. Sloane_, _Robert G. Wilson v_
%E More terms from _Robert G. Wilson v_, Jul 31 2010