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

%I #27 Mar 04 2023 08:56:07

%S 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,

%T 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,

%U 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

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

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

%C 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,...}.

%H Hiroshi Matsui, Masakazu Naito and Naoyuki Totani, <a href="https://scholar.rose-hulman.edu/rhumj/vol10/iss1/9">The Period and the Distribution of the Fibonacci-like Sequence Under Various Moduli</a>, Undergraduate Math Journal, Rose-Hulman Institute of Technology, Vol. 10, Issue 1, 2009.

%H Masakazu Naito and Ryohei Miyadera, <a href="http://www.mi.sanu.ac.rs/vismath/miyadera2009April/JoseVis.html"> The Self-Similarity of the Josephus Problem and its Variants</a>, Visual Mathematics, Volume 11, No.2, 2009.

%H Wolfram MathWorld, <a href="http://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

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

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

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

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

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

%F a(n) = A010872(A054995(n)). - _Gordon Atkinson_, Aug 21 2019

%e 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.

%t 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}]

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

%K nonn

%O 1,2

%A _Ryohei Miyadera_ and Masakazu Naito, Sep 25 2009

%E New name from _Gordon Atkinson_, Aug 21 2019