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

%I #17 Jul 01 2020 22:49:16

%S 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,

%T 21,27,28,23,24,32,33,26,27,36,37,29,30,38,39,32,33,42,43,35,36,48,49,

%U 38,39,52,53,41,42,53,54,44,45,57,58,47,48,65,66,50,51

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

%C 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.

%H Chris Groƫr, <a href="http://www.jstor.org/stable/3647800">The Mathematics of Survival: From Antiquity to the Playground</a>, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

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

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

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

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

%e 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.

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

%Y Cf. A090569, A088442.

%K nonn

%O 1,2

%A _Marcus Hedbring_, May 08 2013