VOOZH about

URL: https://oeis.org/A128982

⇱ A128982 - OEIS


login
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
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
FORMULA
If n is prime, then a(n) = n - 1.
If n is prime + 1, then a(n) = 2.
From Anurup Chakraborty, Feb 01 2026: (Start)
If n is 2 * prime and n + 1 is prime, then a(n) = n - 4.
If n is (prime)^2 and (n + 1)/2 is prime, then a(n) = n - 3.
If both n/3 and (n + 1)/2 are prime, then a(n) = n - 5 (only exception a(9) = 6)
If n is prime + 2 and (n - 1)/2 is prime, then a(n) = 6.
If both (n - 1)/3 and (n - 2)/2 are prime, then a(n) = 8. (End)
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, r; 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