cp's OEIS Frontend

A165556 A symmetric version of the Josephus problem read modulo 2.

%I A165556 #50 May 10 2025 03:20:11
%S A165556 1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,
%T A165556 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,0,1,0,1,0,
%U A165556 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1
%N A165556 A symmetric version of the Josephus problem read modulo 2.
%C A165556 We put n numbers in a circle, and in this variant two numbers are to be eliminated at the same time.
%C A165556 These two processes of elimination go in different directions. Suppose that there are n numbers.
%C A165556 Then the first process of elimination starts with the first number and the 2nd, 4th, 6th numbers, ... are to be eliminated.
%C A165556 The second process starts with the n-th number, and the (n-1)st, (n-3)rd, (n-5)th numbers, ... are to be eliminated.
%C A165556 We suppose that the first process comes first and the second process second at every stage.
%C A165556 We denote the position of the last survivor by JI(n). If we use this sequence under mod 2, then we get the above sequence with 1 and 0.
%C A165556 Old name was "{1,1}, {1, 0, 1, 0}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0}, {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, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0}, ... In this way the two patterns {1,1} and {0,1} take turns in subsequences with the length of 2, 4, 8, 16, 64,...".
%H A165556 Hiroshi Matsui, Toshiyuki Yamauchi, Soh Tatsumi, Takahumi Inoue, Masakazu Naito and Ryohei Miyadera, <a href="http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1652-06.pdf">Interesting Variants of the Josephus Problem</a>, Computer Algebra - Design of Algorithms, Implementations and Applications, Kokyuroku, The Research Institute of Mathematical Science, No. 1652,(2009), 44-54.
%H A165556 Masakazu Naito and Ryohei Miyadera, <a href="http://demonstrations.wolfram.com/TheJosephusProblemInBothDirections/">The Josephus Problem in Both Directions</a>, The Wolfram Demonstrations Project.
%H A165556 Masakazu Naito, Sohtaro Doro, Daisuke Minematsu 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, 11(2) (2009).
%H A165556 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F A165556 a(n) = JI(n) mod 2, and:
%F A165556   JI(8*n) = 4*JI(2*n) - 1 - [JI(2*n)/(n+1)].
%F A165556   JI(8*n+1) = 8*n + 5 - 4*JI(2*n).
%F A165556   JI(8*n+2) = 4*JI(2*n) - 3 - [JI(2*n)/(n+2)].
%F A165556   JI(8*n+3) = 8*n + 7 - 4*JI(2*n).
%F A165556   JI(8*n+4) = 8*n + 8 - 4*JI(2*n+1) + [JI(2*n+1)/(n+2)].
%F A165556   JI(8*n+5) = 4*JI(2*n+1) - 1.
%F A165556   JI(8*n+6) = 8*n + 10 - 4*JI(2*n+1) + [JI(2*n+1)/(n+2)].
%F A165556   JI(8*n+7) = 4*JI(2*n+1) - 3.
%F A165556 where [ ] is the floor function.
%F A165556 Conjecture: a(n) = (1 - (-1)^(n + (n + 1)*floor(log_2(n + 1))))/2. - _Velin Yanev_, Nov 23 2016
%F A165556 a(n) = A325594(n) mod 2. - _Gordon Atkinson_, Oct 06 2019
%e A165556 Suppose that there are n = 14 numbers.
%e A165556 Then the 2nd, 4th, and 6th numbers will be eliminated by the first process. Similarly the 13th, 11th, and 9th numbers will be eliminated by the second process.
%e A165556 Now two directions are going to overlap. The first process will eliminate the 8, 12 and the second process will eliminate 5, 1.
%e A165556 After this the first process will eliminate 3, 14, and the second process will eliminate 10. The number that remains is 7. Therefore JI(14) = 7 and JI(14) = 1 (mod 2).
%t A165556 initialvalue = {1, 1, 3, 4, 3, 6, 1, 3}; Table[JI[n] = initialvalue[[n]], {n, 1, 8}]; JI[m_] := JI[m] = Block[{n, h}, h = Mod[m, 8]; n = (m - h)/8; Which[h == 0, 4 JI[2 n] - 1 - Floor[JI[2 n]/(n + 1)], h == 1, 8 n + 5 - 4 JI[2 n], h == 2, 4 JI[2 n] -3 -Floor[JI[2 n]/(n + 2)], h == 3, 8 n + 7 - 4 JI[2 n], h == 4, 8 n + 8 - 4 JI[2 n + 1] + Floor[JI[2 n + 1]/(n + 2)], h == 5, 4 JI[2 n + 1] - 1, h == 6, 8 n + 10 - 4 JI[2 n + 1] + Floor[JI[2 n + 1]/(n + 2)], h == 7, 4 JI[2 n + 1] - 3]]; Table[Mod[JI[n], 2], {n, 1, 62}]
%t A165556 Flatten[Table[{PadRight[{},2^n,{1}],PadRight[{},2^(n+1),{1,0}]},{n,1,5,2}],1] (* _Harvey P. Dale_, Mar 24 2013 *)
%Y A165556 Cf. A114144, A113648, A325594.
%K A165556 nonn
%O A165556 1,1
%A A165556 _Ryohei Miyadera_ and Masakazu Naito, Sep 22 2009
%E A165556 New name from _Gordon Atkinson_, Sep 06 2019 and Oct 04 2019