A225489 Elimination order for the first person in a linear Josephus problem.

1, 2, 2, 3, 5, 6, 5, 6, 8, 9, 8, 9, 12, 13, 11, 12, 17, 18, 14, 15, 21, 22, 17, 18, 23, 24, 20, 21, 27, 28, 23, 24, 32, 33, 26, 27, 36, 37, 29, 30, 38, 39, 32, 33, 42, 43, 35, 36, 48, 49, 38, 39, 52, 53, 41, 42, 53, 54, 44, 45, 57, 58, 47, 48, 65, 66, 50, 51

Offset: 1

Author

Marcus Hedbring, May 08 2013

Keywords

• nonn

Comments

The process is identical to that of A090569 where n persons are arranged on a line and every second person is eliminated. When we reach the end of the line the direction is reversed without double-counting the person at the end. a(n) is the order in which the person originally first in line is eliminated.

Examples

			If there are 7 persons to begin with, they are eliminated in the following order: 2,4,6,5,1,7,3. So the first person (the person originally first in line) is eliminated as number 5. Therefore a(7) = 5.
		

Links

• Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A090569, A088442.

Programs

Mathematica

t = {1}; Do[AppendTo[t, Switch[Mod[n,4], 0, 3*n/4, 1, t[[1 + (n-1)/4]] + 3*(n-1)/4, 2, t[[1 + (n-2)/4]] + 3*(n-2)/4 + 1, 3, 3*(n-3)/4 + 2, 4, Mod[n,4] + 1]], {n, 2, 100}]; t (* T. D. Noe, May 17 2013 *)

Formula

For n=4m then a(n) = 3*n/4;

for n=4m+1 then a(n) = a(1+(n-1)/4) + 3*(n-1)/4;

for n=4m+2 then a(n) = a(1+(n-2)/4) + 3*(n-2)/4 + 1;

for n=4m+3 then a(n) = 3*(n-3)/4 + 2.