A384991 Order of the permutation of [n] formed by a Josephus elimination variation: take p, skip 1, with p starting at 2 and advancing to the next prime after each skip.

1, 1, 2, 3, 3, 5, 4, 7, 8, 15, 10, 11, 12, 13, 45, 15, 105, 17, 77, 19, 24, 21, 117, 23, 504, 255, 26, 165, 28, 440, 60, 31, 442, 33, 1386, 805, 154, 37, 105, 39, 1020, 216, 208, 43, 40, 45, 2860, 1953, 90, 49, 45, 51, 1092, 120, 184, 55, 56, 150, 58, 6045

Offset: 1

Author

Chuck Seggelin, Jun 14 2025

Keywords

• nonn

Comments

The Josephus elimination begins with a circular list [n] from which successively take p elements and skip 1 where p begins at 2 and increases to the next prime (3,5,7,11,13,...) after each skip, and the permutation is the elements taken in the order they're taken.

Let p(k) be the k-th prime number, and let k increment with each move. In this variation, "take p(k), skip 1" means: move the p(k)-th element to the end of the list. After each move, counting begins from the element that replaced the moved one, and the next move targets the subsequent p(k+1)-th element. Thus, the positions of the elements being moved are p(k+1)-1 apart.

That is, the moved positions follow this progression:

Position Moved Differences Between Positions

=================== =============================

2 - 1 = 1 1 - 0 = 1 (= 2 - 1)

(1) + 3 - 1 = 3 3 - 1 = 2 (= 3 - 1)

(3) + 5 - 1 = 7 7 - 3 = 4 (= 5 - 1)

(7) + 7 - 1 = 13 13 - 7 = 6 (= 7 - 1)

(13) + 11 - 1 = 23 23 - 13 = 10 (= 11 - 1)

^^ . ^^ .

p(k) . p(k)-1 .

. .

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

Examples

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

Links

• Chuck Seggelin, Table of n, a(n) for n = 1..1000

Crossrefs

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

Programs

Python

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