login
Josephus problem: survivors.
(Formerly M0237)
10

%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