|
Search: id:A165556
|
|
|
| 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, 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 two patterns {1,1} and {0,1} take turn in subsequences with the length of 2,4,8,16,64,... |
|
+0
3
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
This is a sequence made by a variant of the Josephus Problem under mod 2.
We put n numbers in a circle, and in this variant two numbers are to be eliminated at the same time.
These two processes of elimination go in different directions. Suppose that there are n-numbers.
Then the first process of elimination starts with the 1st number and the 2-nd, 4-th, 6-th number, ... are to be eliminated.
The second process starts with the n-th number, and the (n-1)-th, (n-3)-th, (n-5)-th number, ... are to be eliminated.
We suppose that the first process comes first and the second process second at every stage.
We denote the position of the survivor by JI(n). If we use this sequence under mod 2, then we get the above sequence with 1 and 0.
|
|
REFERENCES
|
Hiroshi Matsui, Toshiyuki Yamauchi, Soh Tatsumi,Takahumi Inoue,Masakazu Naito and Ryohei Miyadera, "Interesting Variants of the Josephus Problem", Computer Algebra - Design of Algorithms, Implementations and Applications , Kokyuroku, The Research Institute of Mathematical Science, No.1652,(2009), 44-54.
Masakazu Naito, Sohtaro Doro, Daisuke Minematsu and Ryohei Miyadera. The Self-Similarity of the Josephus Problem and its Variants, VISUAL MATHEMATICS, Volume 11, No.2, 2009.
|
|
LINKS
|
Masakazu Naito and Ryohei Miyadera,The Josephus Problem in Both Directions, The Wolfram Demonstrations Project
Masakazu Naito, Sohtaro Doro, Daisuke Minematsu and Ryohei Miyadera. The Self-Similarity of the Josephus Problem and its Variants , VISUAL MATHEMATICS, Volume 11, No.2, 2009.
|
|
FORMULA
|
(1) JI(8n) = 4JI(2n) - 1 - [JI(2n)/(n+1) ].
(2) JI(8n+1) = 8n+5-4JI(2n).
(3) JI(8n+2) = 4JI(2n)-3- [JI(2 n)/(n + 2) ] .
(4) JI(8n+3) = 8n+7-4JI(2n).
(5) JI(8n+4) = 8n+8-4JI(2n+1)+ [JI(2n+1)/(n+2)].
(6) JI(8n+5) = 4JI(2n+1)-1.
(7) JI(8n+6) = 8n+10-4JI(2n+1)+ [(JI(2n+1)/(n+2)].
(8) JI(8n+7) = 4JI(2n+1)-3,
where [ ] is the floor function.
|
|
EXAMPLE
|
Suppose that there are n = 14 numbers.
Then the 2nd, 4th, 6th number will be eliminated by the first process. Similarly 13th, 11th, 9th number will be eliminated by the second process.
Now two directions are going to overlap. The first process will eliminate the 8, 12 and the second process will eliminate 5, 1.
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. JI(14) = 1 (mod 2).
|
|
MATHEMATICA
|
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}]
|
|
CROSSREFS
|
Cf. A114144, A113648
Sequence in context: A071041 A140074 A090174 this_sequence A127243 A127248 A116938
Adjacent sequences: A165553 A165554 A165555 this_sequence A165557 A165558 A165559
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Ryohei Miyadera and Masakazu Naito (miyadera127(AT)aol.com), Sep 22 2009
|
|
|
Search completed in 0.002 seconds
|
