A128982 - OEIS

%I #26 Nov 09 2022 14:20:55

%S 1,1,2,2,4,2,6,2,6,6,10,2,12,2,6,8,16,2,18,2,16,18,22,2,22,12,16,8,28,

%T 2,30,2,28,18,22,12,36,2,6,8,40,2,42,2,30,42,46,2,42,14,40,30,52,2,36,

%U 24,52,54,58,2,60,2,6,30,48,24,66,2,30,18,70,2,72,2,6,20,60,18,78,2,72,78

%N If in a line of n persons every n-th person is eliminated until only one person is left, which position P should one assume in the original lineup to avoid being eliminated?

%C The difference between this, A007495 and the diagonal of A032434 is that for each of the n-1 elimination processes, counting from 1 to n starts at the lowest position in the line that is still occupied, not right after the most recently eliminated position. Wrapping around when n exceeds the number of residual occupied positions still occurs in circular fashion as in the original Josephus problem. - _R. J. Mathar_, May 07 2007

%H Hagen von Eitzen, <a href="/A128982/b128982.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%F If n is prime then P = n - 1. If n is prime + 1 then P = 2.

%e Elimination at n=6: 1,2,3,4,5,6 -> 1,2,3,4,5 -> 2,3,4,5 -> 2,4,5 -> 2,4 -> 2. After the 3 is eliminated, counting does not start at 4 but again at 2.

%p A128982 := proc(n) local l ; l := [seq(i,i=1..n)] ; for i from 1 to n-1 do rm := ((n-1) mod nops(l))+1 ; l := subsop(rm=NULL,l) ; od ; RETURN(op(1,l)) ; end: for n from 1 to 85 do printf("%d, ",A128982(n)) ; od ; # _R. J. Mathar_, May 07 2007

%t a[n_] := Module[{l = Range[n]}, Do[l = Delete[l, Mod[n-1, Length[l]]+1], {n-1}]; If[l == {}, Nothing, l[[1]]]];

%t a /@ Range[0, 100] (* _Jean-François Alcover_, Apr 01 2020 *)

%o (C) int a(int n) { if (n<3) return 1; int L=1, R=n-1, M, t, s, q; while (R>L+1) { s = M = (L+R)/2; t= n-1; while (s && s<t) { q = (n-1)/t; r = q-((n-1)%q); t -= (t+r)/(q+1); s -= (s+r)/(q+1); } if (s) R = M; else L = M; } return R; } /* _Hagen von Eitzen_, Nov 08 2022 */

%Y Cf. A007495, A032434.

%K nonn

%O 1,3

%A _Harri Aaltonen_, Apr 30 2007

%E This is a version of the Josephus problem. Several other versions are already in the OEIS. - _N. J. A. Sloane_, May 01 2007

%E Corrected and extended by _R. J. Mathar_, May 07 2007