A384989 -id:A384989 - cp's OEIS frontend

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

Chuck Seggelin, Jun 14 2025

nonn

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.

			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).

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

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()

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.

Original entry on oeis.org

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

Chuck Seggelin, Jun 14 2025

nonn

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.

			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).

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

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).

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()

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python