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 $a(n)$ ([A057063](https://oeis.org/A057063)).


The sequence begins
$$1, 2, 4, 6, 3, 10, 12, 7, 16, 18, 11, 22, 13, 5, 28$$


Some examples:
$$1,2,(4,3),(6,5),(8,7),(10,9),(12,11),(14,13),(16,15),(18,17)$$
$$1,2,4,(6,5,3),(7,10,8),(12,11,9),(13,16,14),(18,17,15)$$
$$1,2,4,6,(3,7,10,5),(12,11,9,8),(16,14,18,13)$$
$$1,2,4,6,3,(10,5,12,11,7),(8,16,14,18,9)$$


I conjecture that $a(n)+1$ is prime if and only if $a(n)=2(n-1)$.


Is there a way to prove it?



Prime numbers from permutation
**1. Answer to the question.**


**Claim 1.** $a(n)=2(n-1)$ iff the number $d=a(n)$ moves only leftwards (while it moves).


*Proof.* At each move, every moving number moves either to the right or $1$ left.


The number $d=a(n)$ came to the $n$th position during $P(n-1)$, moving $1$ left. If $d$ moved leftwards through all $P(2),\dots, P(n-1)$, then it started at position $n+(n-2)=2(n-1)$ (so $d=2(n-1)$). Otherwise it shifted leftwards by a smaller distance, so it was smaller than $2(n-1)$. $\quad\square$


**Claim 2.** A number $d$ moves only to the left (while it moves) iff $d+1$ is prime.


*Proof.* While $d$ moves to the left, it appears at position $d-i+2$ before $P(i)$. Then, at $P(i)$, it moves to the right iff $d-i+2>i$ and $d-i+2\equiv 1\pmod i$, that is, if $d\equiv -1\pmod i$ and $d+1\geq 2i$, or in other wirds, $i\mid d+1$ and $(d+1)/i>1$.


So, if $p\leq d/2$ is the least prime divisor of $d+1$, then at $P(p)$ the number $d-p+2=(d+1)-(p-1)>p$ shifts to the right (if it did not shift earier --- in fact, it did not). Otherwise, $d$ is prime, and it cannot shift right. $\quad\square$


The two claims yield the result.


**2. Proof that the resulting arrangement is a permutation.**


We fix a number $d$ and describe how it moves. We aim at proving that it shifts rightwards only finitely many times; this clearly yields that $d$ will eventually stop.


Let $a\_n$ denote the position of $d$ before $P(n)$, and put $b\_n=a\_n+n-1$. Informally speaking, $b\_n-1$ denotes a position from which $d$ would come to its current position moving only to the left.


If $d$ moves at $P(n)$, we have $a\_{n+1}=a\_n-1$ if $a\_n\not\equiv 1\pmod n$ and $a\_{n+1}=a\_n+n-1$ otherwise. Therefore, $b\_{n+1}=b\_n$ if $n\nmid b\_n$, and $b\_{n+1}=b\_n+n$ otherwise (in the latter case we call $n$ a *crucial* index); we want to show that there are finitely many crucial indices.


Let $n<m$ be two consecutive crucial indices. Put $c\_n=b\_n/n$; if $c\_n=1$, then $b\_n=n$, and $d$ has just stopped (and $m$ does not exist). Otherwise, if $c\_n>1$, we have $b\_{n+1}=n(c\_n+1)$, and hence $c\_n+1>b\_{n+1}/(n+1)\geq b\_{n+1}/m=b\_m/m=c\_m$. Since $c\_m$ is an integer, we conclude that $c\_m\leq c\_n$.


Number all crucial indices as $n\_1<n\_2<\dots$; put $B\_i=b\_{n\_i}$ and $C\_i=c\_{n\_i}$. Those sequences act as follows:
$$
 C\_i=B\_i/n\_i\leq C\_{i-1}; \quad B\_{i+1}=B\_i+n\_i=n\_i(C\_i+1).
$$
So, while $C\_i$ preserves the value $k>1$, we have $B\_{i+1}=B\_i\cdot \frac{k+1}k$. This may happen only finitely many times if $k>1$, since all the $B\_i$ are integers.


Thus, the (non-increasing) sequence $C\_i$ cannot preserve any value $k>1$ indefinitely, so it decreases from time to time, and eventually it reaches $1$, as desired.


