

A066997


Survivor number for 2ndorder Josephus problem.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,1


COMMENTS

Boyko Bantchev defines the survivor number for the secondorder 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 n1 people, eliminate the one whose ordinal number in the new sequence is a(n1), then do the same with the n2 remaining and so forth, until only one is left. This is the survivor number.


REFERENCES

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


LINKS

Table of n, a(n) for n=2..71.
HsienKuei 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.
HsienKuei Hwang, S. Janson, T.H. Tsai, Exact and Asymptotic Solutions of a DivideandConquer 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


FORMULA

a(n) = 1+k+2^(m1) for k < 2^(m1) and 2^m otherwise, where m = floor(log_2(n)) and k = n2^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.


EXAMPLE

To find a(19): First method: let m = floor(log_2(n)) = 4, let k = n  2^m = 3, then 1 + k + 2^(m1) = 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.


PROG

(PARI) a(n) = my(m = logint(n, 2), k = n  2^m); if (k < 2^(m1), 1+k+2^(m1), 2^m); \\ Michel Marcus, Mar 26 2020


CROSSREFS

This is the same as A006165 except that it lacks two leading 1's.
Sequence in context: A076502 A076897 A316434 * A006165 A078881 A336095
Adjacent sequences: A066994 A066995 A066996 * A066998 A066999 A067000


KEYWORD

easy,nonn


AUTHOR

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


STATUS

approved



