# Prime numbers from permutation

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?

• I don't think "reverse-cyclically permuting every $n$ consecutive terms thereafter" is clear enough, not to me at least. Would you mind posting as an example, in a comment, $P(3)$ of $s(i)=i$? Commented Feb 14, 2022 at 9:47
• @YaakovBaruch, thank you for comment! Done. Commented Feb 14, 2022 at 10:13
• Well, this is easy after you realize that $a(n)=2(n-1)$ iff the number $a(n)$ was shifted only to the left iff $a(n)-((k-2)\not\equiv 1\pmod k$ for all $k<a(n)/2$. Sorry, will fill out details later if necessary. Commented Feb 14, 2022 at 14:33
• At the OEIS page it seems that an open question is whether any integer can be kicked out to infinity. Commented Feb 14, 2022 at 14:43
• When looking at the scatterplot of the sequence it is clear that there are subsequences on other lines. For instance I can numerically spot A131426 as one of the densest lines. Commented Feb 15, 2022 at 10:33

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

• Barring mistakes, up to $n=30000$ the sequence of record breaking pairs $(n,a(n))$ with respect to the ratio $n/a(n)$ is this: $(2,2), (5,3), (14,5), (41,8), (122,14), (365,21), (1094,32), (3281,56), (9842,93), (16403,147), (29525,152)\dots$ and notice that $n_{i+1}=3n_i-1$ provided we ignore the second to last pair! No similar regularity seems apparent in the $a(n_i)$ sequence. Commented Feb 14, 2022 at 21:18
• On further thought, the $(16403,147)$ interloper is probably a result of $n/a(n)$ not necessarily being quite the "correct" metric to define the records. Commented Feb 14, 2022 at 21:40
• I've added a proof that the result is a permutation. It would be interesting to analyze whether this proof may show something about the records listed by @YaakovBaruch. Commented Feb 15, 2022 at 7:15
• Very neat, and much simpler than I was expecting! As for the record breakers, I used a much more natural metric: sorted all pairs $(n,a(n))$ by $a(n)$ and printed those with $n$ higher than all preceding ones. I got the same result, including $(16493,147)$. I think one could probably get out of your proof a bound on $n$ as a function of $a(n)$. Commented Feb 15, 2022 at 9:23
• @Notamathematician I was was doing brute computation of $a(n)$ for all $n$ up to a large number, and reached my limit that way. But it's actually much cheaper to compute $n$ for all $a(n)$ up to a much smaller limit, and thus verify your extra terms. Commented Feb 15, 2022 at 10:37