login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A165556 A symmetric version of the Josephus problem read modulo 2. 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; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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 first number and the 2nd, 4th, 6th numbers, ... are to be eliminated.

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.

We suppose that the first process comes first and the second process second at every stage.

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.

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,...".

LINKS

Table of n, a(n) for n=1..105.

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 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, 11(2) (2009).

Index entries for sequences related to the Josephus Problem

FORMULA

(1) JI(8*n) = 4*JI(2*n) - 1 - [JI(2*n)/(n+1)].

(2) JI(8*n+1) = 8*n + 5 - 4*JI(2n).

(3) JI(8*n+2) = 4*JI(2*n) - 3 - [JI(2*n)/(n + 2)] .

(4) JI(8*n+3) = 8*n + 7 - 4JI(2*n).

(5) JI(8*n+4) = 8*n + 8 - 4*JI(2*n+1) + [JI(2*n+1)/(n + 2)].

(6) JI(8*n+5) = 4*JI(2*n+1) - 1.

(7) JI(8*n+6) = 8*n + 10 - 4*JI(2*n+1) + [(JI(2*n+1)/(n + 2)].

(8) JI(8*n+7) = 4*JI(2*n+1) - 3,

where [ ] is the floor function.

Conjecture: a(n) = (1 - (-1)^(n + (n + 1)*floor(log_2(n + 1))))/2. - Velin Yanev, Nov 23 2016

a(n) = A325594(n) mod 2. -  Gordon Atkinson, Oct 06 2019

EXAMPLE

Suppose that there are n = 14 numbers.

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.

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 and 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}]

Flatten[Table[{PadRight[{}, 2^n, {1}], PadRight[{}, 2^(n+1), {1, 0}]}, {n, 1, 5, 2}], 1] (* Harvey P. Dale, Mar 24 2013 *)

CROSSREFS

Cf. A114144, A113648, A325594.

Sequence in context: A284881 A332823 A090174 * A348292 A127243 A127248

Adjacent sequences:  A165553 A165554 A165555 * A165557 A165558 A165559

KEYWORD

nonn

AUTHOR

Ryohei Miyadera and Masakazu Naito, Sep 22 2009

EXTENSIONS

New name from Gordon Atkinson, Sep 06 2019 and Oct 04 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 26 14:28 EDT 2021. Contains 348267 sequences. (Running on oeis4.)