cp's OEIS Frontend

A186752 Length of minimum representation of the permutation [n,n-1,...,1] as the product of transpositions (1,2) and left and right rotations (1,2,...,n).

%I A186752 #81 Jun 21 2025 16:37:44
%S A186752 0,1,2,4,8,13,19,26,34,43,53,64,76
%N A186752 Length of minimum representation of the permutation [n,n-1,...,1] as the product of transpositions (1,2) and left and right rotations (1,2,...,n).
%C A186752 Example: Taking "0" to indicate the "left" rotation (1,2,...,n) -> (2,3,...,n,1), "1" to represent the transposition (1,2), and "2" to indicate the "right" rotation (1,2,...,n) -> (n,1,2,...n-1), the sequence 10010121 (length = 8) is a minimal sequence producing the reverse permutation on S_5.
%C A186752 It was suggested that a(10) = 61, but this cannot be correct. It would conflict with A186783(10)=45, the diameter of the set under these same operations. We must have a(n) <= A186783(n) for all n. - _Tony Bartoletti_, Mar 08 2019
%C A186752 Conjecture: for n>=4, a(n)=A186783(n)-2. Conjecture holds for n<=13. - _Dmitry Kamenetsky_, Jun 15 2025
%H A186752 Danilo Bazzanella, Antonio Di Scala, Simone Dutto, and Nadir Murru, <a href="https://arxiv.org/abs/2002.08062">Primality tests, linear recurrent sequences and the Pell equation</a>, arXiv:2002.08062 [math.NT], 2020.
%H A186752 Sai Satwik Kuppili, <a href="/A186752/a186752.cpp.txt">C++ program for generating the moves for a given n</a>
%H A186752 Sai Satwik Kuppili and Bhadrachalam Chitturi, <a href="https://arxiv.org/abs/2002.07342">An Upper Bound for Sorting R_n with LRE</a>, arXiv:2002.07342 [cs.DS], 2020.
%o A186752 (Sage) def a186752(n): t = tuple(1..n); G = PermutationGroup([[(1, 2)], [t], PermutationGroupElement([t])^(-1)]); return G.cayley_graph().distance(G.one(),G(list(t)[::-1])) # _Max Alekseyev_, Sep 09 2011
%Y A186752 Cf. A378834 (number of ways), A048200 (LE reversal distance).
%K A186752 nonn,more,hard
%O A186752 1,3
%A A186752 _Tony Bartoletti_, Feb 26 2011
%E A186752 a(9) from _Max Alekseyev_, Sep 09 2011
%E A186752 Incorrect value for a(10) deleted by _N. J. A. Sloane_, Mar 09 2019
%E A186752 a(10) and a(11) added by _Sai Satwik Kuppili_ and _Bhadrachalam Chitturi_, Mar 28 2019
%E A186752 a(12) and a(13) from _Kevin Ryde_, Dec 12 2024