10
$\begingroup$

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?

$\endgroup$
7
  • 3
    $\begingroup$ 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$? $\endgroup$ Commented Feb 14, 2022 at 9:47
  • 1
    $\begingroup$ @YaakovBaruch, thank you for comment! Done. $\endgroup$ Commented Feb 14, 2022 at 10:13
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Feb 14, 2022 at 14:33
  • 2
    $\begingroup$ At the OEIS page it seems that an open question is whether any integer can be kicked out to infinity. $\endgroup$ Commented Feb 14, 2022 at 14:43
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Feb 15, 2022 at 10:33

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 14, 2022 at 21:18
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 14, 2022 at 21:40
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 15, 2022 at 7:15
  • 1
    $\begingroup$ 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)$. $\endgroup$ Commented Feb 15, 2022 at 9:23
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Feb 15, 2022 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.