The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A066997 Survivor number for 2nd-order 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 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. 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. 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. EXAMPLE 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. PROG (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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 20 03:55 EDT 2020. Contains 337264 sequences. (Running on oeis4.)