OFFSET
1,5
COMMENTS
The Josephus elimination begins with a circular list [n] from which successively take 3 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 [n] and applying the "skip" as a move (rotate) of the element at position 3*i+4 to the end of the list, for successive i >= 0.
Take 3 and move 1 is a move every 4th element, but with the next 4 elements reckoned inclusive of the element which replaced the moved 1, and hence positions 3 apart.
A given element can be skipped or moved multiple times before reaching its final position.
LINKS
Chuck Seggelin, Table of n, a(n) for n = 1..1000
EXAMPLE
For n=11, the rotations to construct the permutation are
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
\------------------------/ 1st rotation
1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 4
\---------------/ 2nd rotation
1, 2, 3, 5, 6, 7, 9, 10, 11, 4, 8
\----/ 3rd rotation
1, 2, 3, 5, 6, 7, 9, 10, 11, 8, 4
The 3rd rotate is an example of an element (4) which was previously rotated to the end, being rotated to the end again.
This final permutation has order a(11) = 6 (applying it 6 times reaches the identity permutation again).
PROG
(Python)
from sympy.combinatorics import Permutation
def move_fourth(seq):
for i in range(3, len(seq), 3):
seq.append(seq.pop(i))
return seq
def a(n):
seq = list(range(n))
p = move_fourth(seq.copy())
return Permutation(p).order()
CROSSREFS
KEYWORD
nonn
AUTHOR
Chuck Seggelin, Jun 14 2025
STATUS
approved