

A128982


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


4



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The difference between this, A007495 and the diagonal of A032434 is that for each of the n1 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


LINKS



FORMULA

If n is prime then P = n  1. If n is prime + 1 then P = 2.


EXAMPLE

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.


MAPLE

A128982 := proc(n) local l ; l := [seq(i, i=1..n)] ; for i from 1 to n1 do rm := ((n1) 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


MATHEMATICA

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


PROG

(C) int a(int n) { if (n<3) return 1; int L=1, R=n1, M, t, s, q; while (R>L+1) { s = M = (L+R)/2; t= n1; while (s && s<t) { q = (n1)/t; r = q((n1)%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 */


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS

This is a version of the Josephus problem. Several other versions are already in the OEIS.  N. J. A. Sloane, May 01 2007


STATUS

approved



