A057063 - OEIS

%I #44 Aug 16 2024 21:10:38

%S 1,2,4,6,3,10,12,7,16,18,11,22,13,5,28,30,19,20,36,23,40,42,9,46,29,

%T 31,52,37,35,58,60,15,44,66,43,70,72,25,54,78,8,82,61,55,88,65,59,68,

%U 96,27,100,102,38,106,108,71,112,85,33,89,94,79,48,126,83,130

%N 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 A057063.

%C It appears that this is a permutation of the integers. - _Michel Marcus_, Feb 19 2016

%C 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

%C From _Jianing Song_, Sep 27 2023: (Start)

%C 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.

%C 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}.

%C 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.

%C 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)

%H MathOverflow, <a href="https://mathoverflow.net/q/416089/17581">Prime numbers from permutation</a>, 2022.

%F Conjecture: a(n) = A057033(n-1) + 1 for n > 1 with a(1) = 1. - _Mikhail Kurkov_, Mar 10 2022

%e PS(2) begins with 1,2,4,3,6,5,8;

%e PS(3) begins with 1,2,4,6,5,3,7;

%e PS(4) begins with 1,2,4,6,3,7,10.

%o (PARI) get(v, iv) = if (iv > #v, 0, v[iv]);

%o 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;}

%o 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

%Y Cf. A007062, A057030, A057032, A057033, A057064.

%K nonn

%O 1,2

%A _Clark Kimberling_, Aug 01 2000