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

Author

Harri Aaltonen, Apr 30 2007

Keywords

• nonn

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

Examples

			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.
		

Links

• Hagen von Eitzen, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A007495, A032434.

Programs

C

int a(int n) { if (n<3) return 1; int L=1, R=n-1, M, t, s, q, r; while (R>L+1) { s = M = (L+R)/2; t= n-1; while (s && sHagen von Eitzen, Nov 08 2022 */

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

Formula

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

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