

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

Table of n, a(n) for n=1..67.
Index entries for sequences related to the Josephus Problem


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

Cf. A006257.
Sequence in context: A102257 A091425 A205005 * A104612 A088392 A195699
Adjacent sequences: A113645 A113646 A113647 * A113649 A113650 A113651


KEYWORD

easy,nonn


AUTHOR

Satoshi Hashiba, Daisuke Minematsu and Ryohei Miyadera, Jan 15 2006


STATUS

approved



