login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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? 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 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
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
Sequence in context: A002322 A127835 A117004 * A096216 A121599 A360593
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 23:53 EDT 2024. Contains 373535 sequences. (Running on oeis4.)