A128982 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?

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

Offset

1,3

Comments

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

Links

Hagen von Eitzen, Table of n, a(n) for n = 1..10000

Index entries for sequences related to the Josephus Problem

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 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

Mathematica

a[n_] := Module[{l = Range[n]}, Do[l = Delete[l, Mod[n-1, Length[l]]+1], {n-1}]; If[l == {}, Nothing, l[[1]]]];
a /@ Range[0, 100] (* Jean-François Alcover, Apr 01 2020 *)

Prog

(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 */

Crossrefs

Cf. A007495, A032434.

Sequence in context: A002322 A127835 A117004 * A096216 A121599 A360593

Adjacent sequences: A128979 A128980 A128981 * A128983 A128984 A128985

Keyword

nonn

Author

Harri Aaltonen, Apr 30 2007

Extensions

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

Corrected and extended by R. J. Mathar, May 07 2007

Status

approved