A048200 Minimal length pair-exchange / set-rotate sequence to reverse n distinct ordered elements.

0, 1, 2, 4, 10, 15, 23, 32, 42, 55, 67, 84, 98, 119

Offset: 1

Author

Tony Bartoletti

Keywords

• nonn
• nice
• more

Comments

"Rotate" is always a left-rotate (moves leftmost element to the right end) and "Exchange" is always a pair-exchange of the two leftmost elements.

a(15)<=135 and a(16)<=160. See example solutions in the links section. - Dmitry Kamenetsky, Jun 19 2025

Examples

			a(4) = 4 since "xrrx" is the shortest sequence reversing "ABCD". Explicitly, (begin) ABCD, (x)-> BACD, (r)-> ACDB, (r) -> CDBA, (x)-> DCBA.
		

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.
• Sean A. Irvine, Java program (github)
• Dmitry Kamenetsky, Best known solutions for n <= 16.
• Sai Satwik Kuppili, C++ program for generating the moves for a given n
• Sai Satwik Kuppili and Bhadrachalam Chitturi, Exact upper bound for sorting R_n with LE, University of Texas at Dallas (2019).
• Sai Satwik Kuppili and Bhadrachalam Chitturi, An upper bound for sorting R_n with LRE, arXiv:2002.07342 [cs.DS], 2020.
• Sai Satwik Kuppili and Bhadrachalam Chitturi, Exact upper bound for sorting R_n with LE, Discrete Mathematics, Algorithms and Applications, 2020.
• Kevin Ryde, C Code

Crossrefs

Cf. A058986, A065603, A186752.

Programs

C

/* See links. */

Java

/* See links. */

Formula

Conjecture: a(n) = (3*n^2/4)-2*n if n is even and a(n) = (3*n^2-10*n+15)/4 if n is odd. See links for more information. - Sai Satwik Kuppili and Bhadrachalam Chitturi, Jun 09 2020

Extensions

a(11) added by Sai Satwik Kuppili and Srinath T, Bhadrachalam Chitturi, Jan 02 2019

a(12) from Sean A. Irvine, Jun 04 2021

a(13) from Kevin Ryde, Dec 19 2024

a(14) from Zachary DeStefano, Jan 03 2025