A066997 Survivor number for 2nd-order Josephus problem.

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, 16, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 35, 36, 37, 38, 39, 40

Offset: 2

Author

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

Keywords

• easy
• nonn

Comments

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.

Examples

			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.
		

References

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

Links

• Hsien-Kuei Hwang, S. Janson, T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
• Hsien-Kuei Hwang, S. Janson, T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
• Index entries for sequences related to the Josephus Problem

Crossrefs

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

Programs

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

Formula

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.