A384990 Order of the permutation of [n] formed by a Josephus elimination variation: take k, skip 1, with k starting at 1 and increasing by 1 after each skip.

1, 1, 2, 2, 4, 5, 6, 7, 15, 9, 12, 11, 12, 13, 14, 60, 16, 70, 24, 88, 20, 60, 22, 23, 24, 25, 26, 27, 420, 29, 221, 31, 3465, 33, 285, 35, 840, 37, 38, 1040, 40, 41, 2618, 43, 44, 2520, 46, 546, 48, 594, 840, 644, 52, 696, 54, 2520, 56, 57, 58, 59, 60, 61, 62

Offset: 1

Author

Chuck Seggelin, Jun 14 2025

Keywords

• nonn

Comments

The Josephus elimination begins with a circular list [n] from which successively take k elements and skip 1 where k begins at 1 and monotonically increases after each skip, and the permutation is the elements taken in the order they're taken.

Take k and move 1 is a move every k-th element, but with the next k+1 elements reckoned inclusive of the element which replaced the moved 1, and hence positions k apart.

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

This sequence enters relatively lengthy stretches of linearity where a(n) = n-1 before entering stretches where it oscillates between n-1 and much larger values. This behavior is observed multiple times between a(1) and a(1000). It is unknown if this behavior continues to happen further into the sequence. For example: a(n)=n-1 for n=905 to 946, and the terms that follow are 9419588158802421600, 947, 224555, 949, 1582305192, 951, 226455, 953, etc.

Examples

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

Crossrefs

Cf. A051732 (Josephus elimination permutation order), A384753 (take 2 skip 1 Josephus variation), A384989 (take 3 skip 1 Josephus variation).

Programs

Python

from sympy.combinatorics import Permutation
def apply_transformation(seq):
    step = 1
    i = step
    while i < len(seq):
        seq.append(seq.pop(i))
        step += 1
        i += step - 1
    return seq
def a(n):
    seq = list(range(n))
    p = apply_transformation(seq.copy())
    return Permutation(p).order()