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

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

Offset: 1

Author

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

Keywords

• easy
• nonn

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.

Examples

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

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley

Links

• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A006257.

Programs

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]];

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).