A165735 Surviving integers under the double-count Josephus problem (see A054995), modulo 3.

1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Author

Ryohei Miyadera and Masakazu Naito, Sep 25 2009

Keywords

• nonn

Comments

Old name was: The pattern is obvious. The sequence can be divided into subsequences of {1,1,1,...} and {2,2,2,...}.

Let n be a natural number. We put n numbers in a circle, and we are going to remove every third number. Let J3(n) be the last number that remains. This is the traditional Josephus Problem. Let J3 (mod 3) be the residue of the sequence J3(n) under mod 3. J3 (mod 3) produces the sequence {1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2,...}.

Examples

			If we use n = 10, then we put numbers 1,2,3,4,5,6,7,8,9,10 in a circle. We eliminate 3,6,9,2,7,1,8,5,10, and the last number that remains is 4. Therefore J3(10) = 4 and J3(10) = 1 mod 3.
		

Links

• Hiroshi Matsui, Masakazu Naito and Naoyuki Totani, The Period and the Distribution of the Fibonacci-like Sequence Under Various Moduli, Undergraduate Math Journal, Rose-Hulman Institute of Technology, Vol. 10, Issue 1, 2009.
• Masakazu Naito and Ryohei Miyadera, The Self-Similarity of the Josephus Problem and its Variants, Visual Mathematics, Volume 11, No.2, 2009.
• Wolfram MathWorld, Josephus Problem
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A010872, A054995, A114144, A113648, A165556.

Programs

Mathematica

J3[1] = 1; J3[2] = 2; J3[n_] := J3[n] = Block[{m, t}, t = Mod[n, 3]; m = (n - t)/3; Which[t == 0, J3[2 m] + Floor[(J3[2 m] - 1)/2], t == 1, If[J3[2 m + 1] == 1, 3 m + 1, J3[2 m + 1] + Floor[J3[2 m + 1]/2] - 2], t == 2, J3[2 m + 1] + Floor[J3[2 m + 1]/2] + 1]]; Table[Mod[J3[n], 3], {n, 1, 200}]

Formula

(1) J3(1) = 1 and J3(2) = 2.

(2) J3(3m) = J3(2m) + [(J3(2m)-1)/2].

(3a) J3(3m+1) = 3m + 1 (if J3(2m + 1) = 1).

(3b) J3(3m+1) = J3(2m+1) + [J3(2m+1)/2] - 2 (if J3(2m + 1) > 1).

(4) J3(3m+2) = J3(2m+1) + [J3(2m+1)/2] + 1

a(n) = A010872(A054995(n)). - Gordon Atkinson, Aug 21 2019

Extensions

New name from Gordon Atkinson, Aug 21 2019