A384753 Order of the permutation of {1,...,n} formed by a Josephus elimination variation: take 2, skip 1.

1, 1, 1, 2, 3, 3, 5, 6, 4, 7, 9, 10, 5, 9, 13, 70, 12, 15, 84, 70, 52, 42, 21, 30, 15, 16, 38, 84, 168, 24, 90, 360, 120, 27, 24, 72, 30, 108, 286, 276, 105, 4680, 198, 36, 630, 234, 120, 2856, 54, 1056, 532, 660, 51, 310, 406, 54, 420, 120, 55, 264, 150

Offset: 1

Author

Chuck Seggelin, Jun 09 2025

Keywords

• nonn

Comments

The Josephus elimination begins with a circular list {1,...,n} from which successively take 2 elements and skip 1, and the permutation is the elements taken in the order they're taken.

The same effect can be had by leaving remaining elements at the end of a flat list of {1,...,n} and applying the "skip" as a move (rotate) of the element at position 2*i+3 to the end of the list, for successive i >= 0.

Take 2 and move 1 is a move every 3rd element, but with the next 3 elements reckoned inclusive of the element which replaced the moved 1, and hence positions 2 apart.

A given element can be skipped or moved multiple times before reaching its final position.

The value of a(n) can vary sharply; for example, a(62) = 280, a(63) = 15939, a(64) = 210.

Examples

			For n=10, the rotations to construct the permutation are
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10
          \-----------------------/  1st rotation
    1, 2, 4, 5, 6, 7, 8, 9, 10, 3
                \-----------------/  2nd rotation
    1, 2, 4, 5, 7, 8, 9, 10, 3, 6
                      \-----------/  3rd rotation
    1, 2, 4, 5, 7, 8, 10, 3, 6, 9
                             \----/  4th rotation
    1, 2, 4, 5, 7, 8, 10, 3, 9, 6
The 4th rotate is an example of an element (6) which was previously rotated to the end, being rotated to the end again.
This final permutation has order a(10) = 7 (applying it 7 times reaches the identity permutation again).
		

Crossrefs

Cf. A051732 (Josephus elimination permutation order).

Programs

Python

from sympy.combinatorics import Permutation
def move_third(seq):
    for i in range(2,len(seq),2):
        seq.append(seq.pop(i))
    return seq
def a(n):
    seq = list(range(n))
    p = move_third(seq.copy())
    return Permutation(p).order()