Prime numbers from permutation

Question

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

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?

Answer 1

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.