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

Author

Clark Kimberling, Aug 01 2000

Keywords

• nonn

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)

Examples

			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.
		

Links

• MathOverflow, Prime numbers from permutation, 2022.

Crossrefs

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

Programs

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

Formula

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