A057063 Let P(n) of a sequence s(1),s(2),s(3),... be obtained by leaving s(1),...,s(n) fixed and reverse-cyclically permuting every n consecutive terms thereafter; apply P(2) to 1,2,3,... to get PS(2), then apply P(3) to PS(2) to get PS(3), then apply P(4) to PS(3), etc. The limit of PS(n) is A057063.

1, 2, 4, 6, 3, 10, 12, 7, 16, 18, 11, 22, 13, 5, 28, 30, 19, 20, 36, 23, 40, 42, 9, 46, 29, 31, 52, 37, 35, 58, 60, 15, 44, 66, 43, 70, 72, 25, 54, 78, 8, 82, 61, 55, 88, 65, 59, 68, 96, 27, 100, 102, 38, 106, 108, 71, 112, 85, 33, 89, 94, 79, 48, 126, 83, 130

Offset

1,2

Comments

It appears that this is a permutation of the integers. - Michel Marcus, Feb 19 2016

The fact that this is a permutation is proved at the MathOverflow link below. Also from that link: a(n)+1 is prime if and only if a(n) = 2*(n-1). - Ilya I. Bogdanov, Feb 15 2022

From Jianing Song, Sep 27 2023: (Start)

Let {b(n)} be the inverse permutation of this sequence, then each number n >= 3 is moved for b(n)-2 times during the process.

Proof: suppose that this number is k, which is well-defined since PS(1), PS(2), ... has a limit. Suppose that PS(i+1)(c_i) = n for each i >= 0, that is, c_i is the index of n after i steps. In the (i+1)-th step, each group of PS(i+1) contains i+2 elements, and every element is moved if and only if it has index at least i+3. We obtain that k = #{i >= 0 : c_i >= i+3}.

Note that if c_i <= i+2 for some i, then from the (i+1)-th step on, each group contains at least i+2 numbers so the first i+2 numbers in the sequence remain fixed, which means that n = PS(i+1)(c_i) = PS(i+2)(c_i) = ... = a(c_i), so c_i = c_{i+1} = ... = b(n). This shows that {i >= 0 : c_i >= i+3} = {0, 1, ..., k-1}, which implies that k is the smallest number such that c_k <= k+2. On one hand, since c_k <= k+2, we have c_k = b(n), so b(n) <= k+2. On the other hand, from the (b(n)-1)-th step on, each group contains at least b(n) numbers so the first b(n) numbers in the sequence remain fixed, which means that PS(b(n)-1)(b(n)) = PS(b(n))(b(n)) = ... = a(b(n)) = n, so c_{b(n)-2} = b(n), and k <= b(n)-2. In conclusion, we have k = b(n)-2.

By the MathOverflow link, we have a(n) <= 2*n-2 for all n, where the equality holds if and only if a(n)+1 is prime. On the other hand, it is hard to get a lower bound for {a(n)}, so it is infeasible to calculate the inverse permutation of this sequence. (End)

Links

Table of n, a(n) for n=1..66.

MathOverflow, Prime numbers from permutation, 2022.

Formula

Conjecture: a(n) = A057033(n-1) + 1 for n > 1 with a(1) = 1. - Mikhail Kurkov, Mar 10 2022

Example

PS(2) begins with 1,2,4,3,6,5,8;
PS(3) begins with 1,2,4,6,5,3,7;
PS(4) begins with 1,2,4,6,3,7,10.

Prog

(PARI) get(v, iv) = if (iv > #v, 0, v[iv]);
rcp(nbn, nbp, startv, v) = {w = vector(nbn); for (k=1, nbn, if (k % nbp, jv = startv+k, jv = startv+k-nbp); w[k] = get(v, jv); ); w; }
lista(nn) = {v = vector(nn, n, n); print1(v[1], ", ", v[2], ", "); startv = 3; for (n=3, nn, w = rcp(nn-n+1, n-1, startv, v); startv = 2; if (w[1] == 0, break); print1(w[1], ", "); v = w; ); } \\ Michel Marcus, Feb 19 2016

Crossrefs

Cf. A007062, A057030, A057032, A057033, A057064.

Sequence in context: A338059 A258105 A331525 * A108236 A002849 A329492

Adjacent sequences: A057060 A057061 A057062 * A057064 A057065 A057066

Keyword

nonn

Author

Clark Kimberling, Aug 01 2000

Status

approved