|
%I #43 Jun 23 2020 18:11:56
%S 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 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 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 A symmetric version of the Josephus problem read modulo 2.
%C We put n numbers in a circle, and in this variant two numbers are to be eliminated at the same time.
%C These two processes of elimination go in different directions. Suppose that there are n numbers.
%C Then the first process of elimination starts with the first number and the 2nd, 4th, 6th numbers, ... are to be eliminated.
%C 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 We suppose that the first process comes first and the second process second at every stage.
%C 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 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 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 Masakazu Naito and Ryohei Miyadera, <a href="http://demonstrations.wolfram.com/TheJosephusProblemInBothDirections/">The Josephus Problem in Both Directions</a>, The Wolfram Demonstrations Project.
%H 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 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F (1) JI(8*n) = 4*JI(2*n) - 1 - [JI(2*n)/(n+1)].
%F (2) JI(8*n+1) = 8*n + 5 - 4*JI(2n).
%F (3) JI(8*n+2) = 4*JI(2*n) - 3 - [JI(2*n)/(n + 2)] .
%F (4) JI(8*n+3) = 8*n + 7 - 4JI(2*n).
%F (5) JI(8*n+4) = 8*n + 8 - 4*JI(2*n+1) + [JI(2*n+1)/(n + 2)].
%F (6) JI(8*n+5) = 4*JI(2*n+1) - 1.
%F (7) JI(8*n+6) = 8*n + 10 - 4*JI(2*n+1) + [(JI(2*n+1)/(n + 2)].
%F (8) JI(8*n+7) = 4*JI(2*n+1) - 3,
%F where [ ] is the floor function.
%F Conjecture: a(n) = (1 - (-1)^(n + (n + 1)*floor(log_2(n + 1))))/2. - _Velin Yanev_, Nov 23 2016
%F a(n) = A325594(n) mod 2. - _Gordon Atkinson_, Oct 06 2019
%e Suppose that there are n = 14 numbers.
%e 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 Now two directions are going to overlap. The first process will eliminate the 8, 12 and the second process will eliminate 5, 1.
%e 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 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 Flatten[Table[{PadRight[{},2^n,{1}],PadRight[{},2^(n+1),{1,0}]},{n,1,5,2}],1] (* _Harvey P. Dale_, Mar 24 2013 *)
%Y Cf. A114144, A113648, A325594.
%K nonn
%O 1,1
%A _Ryohei Miyadera_ and Masakazu Naito, Sep 22 2009
%E New name from _Gordon Atkinson_, Sep 06 2019 and Oct 04 2019
|
