OFFSET
1,4
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.
EXAMPLE
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).
PROG
(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()
CROSSREFS
KEYWORD
nonn
AUTHOR
Chuck Seggelin, Jun 09 2025
STATUS
approved