login
Survivor number for 2nd-order Josephus problem.
1

%I #21 Jun 23 2020 18:52:05

%S 2,2,3,4,4,4,5,6,7,8,8,8,8,8,9,10,11,12,13,14,15,16,16,16,16,16,16,16,

%T 16,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,32,32,32,32,32,

%U 32,32,32,32,32,32,32,32,32,32,32,33,34,35,36,37,38,39,40

%N Survivor number for 2nd-order Josephus problem.

%C Boyko Bantchev defines the survivor number for the second-order Josephus problem with n persons as follows: a(n) is not the number of the actual survivor but that of the person to be eliminated; that is, every second person in a circle is marked until only one remains - and that one is eliminated; having eliminated a(n), start again from the beginning with the remaining n-1 people, eliminate the one whose ordinal number in the new sequence is a(n-1), then do the same with the n-2 remaining and so forth, until only one is left. This is the survivor number.

%D Boyko Bantchev (bantchev(AT)math.bas.bg), Personal communication, Nov 30 2001

%H Hsien-Kuei Hwang, S. Janson, T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.

%H Hsien-Kuei Hwang, S. Janson, T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

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

%F a(n) = 1+k+2^(m-1) for k < 2^(m-1) and 2^m otherwise, where m = floor(log_2(n)) and k = n-2^m. Also: write n in binary; drop first bit; "OR" new first bit with each remaining bit; append 1 as new first bit; convert to integer; add 1.

%e To find a(19): First method: let m = floor(log_2(n)) = 4, let k = n - 2^m = 3, then 1 + k + 2^(m-1) = 12. Binary method: 19 in binary is 1 0 0 1 1; drop first bit leaving 0 0 1 1; "OR" first bit with remaining bits giving 0 1 1; append leading 1 giving 1 0 1 1; convert to integer giving 11; add 1 giving 12.

%o (PARI) a(n) = my(m = logint(n, 2), k = n - 2^m); if (k < 2^(m-1), 1+k+2^(m-1), 2^m); \\ _Michel Marcus_, Mar 26 2020

%Y This is the same as A006165 except that it lacks two leading 1's.

%K easy,nonn

%O 2,1

%A Eugene McDonnell (eemcd(AT)aol.com), Jan 27 2002