A090569 The survivor w(n,2) in a modified Josephus problem, with a step of 2.

1, 1, 3, 3, 1, 1, 3, 3, 9, 9, 11, 11, 9, 9, 11, 11, 1, 1, 3, 3, 1, 1, 3, 3, 9, 9, 11, 11, 9, 9, 11, 11, 33, 33, 35, 35, 33, 33, 35, 35, 41, 41, 43, 43, 41, 41, 43, 43, 33, 33, 35, 35, 33, 33, 35, 35, 41, 41, 43, 43, 41, 41, 43, 43, 1, 1, 3, 3, 1, 1, 3, 3, 9, 9, 11, 11, 9, 9, 11, 11, 1, 1

Offset

1,3

Comments

Arrange n persons {1,2,...,n} consecutively on a line rather than around in a circle. Beginning at the left end of the line, we remove every q-th person until we reach the end of the line. At this point we immediately reverse directions, taking care not to "double count" the person at the end of the line and continue to eliminate every q-th person, but now moving right to left. We continue removing people in this back-and-forth manner until there remains a lone survivor w(n,q).

Or a(n) is in A145812 such that 2n+1-2a(n) is in A145812 as well. Note also that 2a(n)+A088442(n-1)=2n+1. - Vladimir Shevelev, Oct 20 2008

Links

Table of n, a(n) for n=1..82.

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

Index entries for sequences related to the Josephus Problem

Formula

w(n, 2) = 1 + Sum_{odd j=1..k} b(j)*(2^j), where Sum_{j=0..k} b(j)*(2^j) is the binary expansion of either n or n-1, whichever is odd.

a(n) = A063695(n-1) + 1.

Example

a(2)=11, since people are eliminated in the order 2, 4, 6, 8, 10, 12, 9, 5, 1, 7, 3, leaving 11 as the survivor.

Prog

(Python)
def A090569(n): return (n-1&((1<<(m:=(n-1).bit_length())+(m&1^1))-1)//3)+1 # Chai Wah Wu, Jan 30 2023

Crossrefs

Cf. A088443, A088452.

Sequence in context: A266529 A266509 A266539 * A160324 A347026 A197928

Adjacent sequences: A090566 A090567 A090568 * A090570 A090571 A090572

Keyword

nonn

Author

John W. Layman, Dec 02 2003

Status

approved