

A113648


A variant of Josephus Problem in which 2 persons are to be eliminated at the same time.


4



1, 3, 6, 1, 3, 5, 7, 9, 12, 15, 18, 21, 24, 27, 30, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 1, 3, 5, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

a(n) is defined as follows. Write the numbers 1 through 2n in a circle, start at 1 and n+1. Cross off every other number until only one number is left. The process that starts with 1 should be the first at any stage. For example we cross off 2, n+2, 4, n+4, 6, n+6, .... The remaining number is a(n). This function is defined only for even arguments.


REFERENCES

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley


LINKS



FORMULA

The sequence a(m) is defined for any even number m as follows: a(2) = 1. a(4*n) = 2*a(2*n)  2*n  1 (if a(2*n) > n) and a(4*n) = 2*a(2*n) + 2*n  1 (if a(2*n) <= n). a(4*n+2) = 2*a(2*n+2)  2*n  5 (if a(2*n+2) >= n + 3), a(4*n+2) = 2*a(2*n+2) + 2*n  2 (if n + 3 > a(2*n+2) >= 2), and a(4*n+2) = 2*n+1 (if a(2*n+2) = 1).


EXAMPLE

For a(8): we are to cross off 2, 6, 4, 8, 7, 3, 5 and 1 is left. Therefore a(8) = 1.


MATHEMATICA

jose2[2] = 1; jose2[n_] := If[Mod[n, 4] == 0, If[jose2[n/2] <= (n/4), 2(n/4) + 2jose2[n/2]  1, 2jose2[n/2]  2(n/4)  1], Which[jose2[(n + 2)/2] == 1, n/2, 1 < jose2[(n + 2)/2] < (n + 10)/4, 2jose2[(n + 2)/2] + (n  2)/2  2, (n + 6)/4 < jose2[(n + 2)/2], 2jose2[(n + 2)/2]  (n + 8)/2]];


CROSSREFS



KEYWORD

easy,nonn


AUTHOR



STATUS

approved



