cp's OEIS Frontend

A066997 Survivor number for 2nd-order Josephus problem.

%I A066997 #21 Jun 23 2020 18:52:05
%S A066997 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 A066997 16,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,32,32,32,32,32,
%U A066997 32,32,32,32,32,32,32,32,32,32,32,33,34,35,36,37,38,39,40
%N A066997 Survivor number for 2nd-order Josephus problem.
%C A066997 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 A066997 Boyko Bantchev (bantchev(AT)math.bas.bg), Personal communication, Nov 30 2001
%H A066997 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 A066997 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 A066997 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F A066997 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 A066997 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 A066997 (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 A066997 This is the same as A006165 except that it lacks two leading 1's.
%K A066997 easy,nonn
%O A066997 2,1
%A A066997 Eugene McDonnell (eemcd(AT)aol.com), Jan 27 2002