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

0, 1, 2, 4, 8, 13, 19, 26, 34, 43, 53, 64, 76

Offset: 1

Author

Tony Bartoletti, Feb 26 2011

Keywords

• nonn
• more
• hard

Comments

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.

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

Conjecture: for n>=4, a(n)=A186783(n)-2. Conjecture holds for n<=13. - Dmitry Kamenetsky, Jun 15 2025

Links

• Danilo Bazzanella, Antonio Di Scala, Simone Dutto, and Nadir Murru, Primality tests, linear recurrent sequences and the Pell equation, arXiv:2002.08062 [math.NT], 2020.
• Sai Satwik Kuppili, C++ program for generating the moves for a given n
• Sai Satwik Kuppili and Bhadrachalam Chitturi, An Upper Bound for Sorting R_n with LRE, arXiv:2002.07342 [cs.DS], 2020.

Crossrefs

Cf. A378834 (number of ways), A048200 (LE reversal distance).

Programs

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

Extensions

a(9) from Max Alekseyev, Sep 09 2011

Incorrect value for a(10) deleted by N. J. A. Sloane, Mar 09 2019

a(10) and a(11) added by Sai Satwik Kuppili and Bhadrachalam Chitturi, Mar 28 2019

a(12) and a(13) from Kevin Ryde, Dec 12 2024