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
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
KEYWORD
nonn
AUTHOR
Clark Kimberling, Aug 01 2000
STATUS
approved