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

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.

Links

Table of n, a(n) for n=1..68.

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

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.

Example

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.

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

Crossrefs

Cf. A090569, A088442.

Sequence in context: A137756 A333468 A364971 * A308773 A051732 A098382

Adjacent sequences: A225486 A225487 A225488 * A225490 A225491 A225492

Keyword

nonn

Author

Marcus Hedbring, May 08 2013

Status

approved