A000376 Topswops (2): start by shuffling n cards labeled 1..n. If the top card is m, reverse the order of the top m cards. Repeat until 1 gets to the top, then stop. Suppose the whole deck is now sorted (if not, discard this case). a(n) is the maximal number of steps before 1 got to the top.

0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 63, 80, 101, 112, 130, 159, 191, 207, 231

Offset

1,3

Comments

See also A000375, which is the main entry for this problem.

Comments from Joshua Zucker, Jan 24 2007: (Start)

For some n, there are some longest chains which end up sorted and some which don't, like n = 6, with the following four chains that end sorted and one that does not:

The examples below use 0 through n-1 instead of 1 through n.

((#(4 5 3 0 2 1) #(2 0 3 5 4 1) #(3 0 2 5 4 1) #(5 2 0 3 4 1) #(1 4 3 0 2 5) #(4 1 3 0 2 5) #(2 0 3 1 4 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5))

(#(3 4 5 1 0 2) #(1 5 4 3 0 2) #(5 1 4 3 0 2) #(2 0 3 4 1 5) #(3 0 2 4 1 5) #(4 2 0 3 1 5) #(1 3 0 2 4 5) #(3 1 0 2 4 5) #(2 0 1 3 4 5) #(1 0 2 3 4 5) #(0 1 2 3 4 5))

(#(3 0 4 1 5 2) #(1 4 0 3 5 2) #(4 1 0 3 5 2) #(5 3 0 1 4 2) #(2 4 1 0 3 5) #(1 4 2 0 3 5) #(4 1 2 0 3 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5))

(#(2 5 4 0 3 1) #(4 5 2 0 3 1) #(3 0 2 5 4 1) #(5 2 0 3 4 1) #(1 4 3 0 2 5) #(4 1 3 0 2 5) #(2 0 3 1 4 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5)))

(#(3 0 5 4 1 2) #(4 5 0 3 1 2) #(1 3 0 5 4 2) #(3 1 0 5 4 2) #(5 0 1 3 4 2) #(2 4 3 1 0 5) #(3 4 2 1 0 5) #(1 2 4 3 0 5) #(2 1 4 3 0 5) #(4 1 2 3 0 5) #(0 3 2 1 4 5))

And for some n, e.g., n=12, none of the longest chains end up sorted (and hence A000375 and A000376 are different). I did an exhaustive search with n = 12 working backwards from sorted and found 63 as the longest chain beginning with one of these four:

#(9 10 6 0 2 7 1 8 11 5 3 4)

#(9 10 6 0 1 2 7 8 11 5 3 4)

#(7 8 11 5 0 6 10 9 2 1 3 4)

#(5 0 1 7 10 3 11 8 9 6 2 4)

But 65 is attainable if you don't assume it ends up sorted. (End)

Comment from Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010: (Start)

(6 14 9 2 15 8 1 3 4 12 18 5 10 13 16 17 11 7) is the only permutation of length 18 that takes 191 steps (also called longest-winded permutation) of "topswopping moves" before it goes to the identity permutation (i.e., in sorted order).

For n=17, (2 10 15 11 7 14 5 16 6 4 17 13 1 3 8 9 12) is the only longest-winded permutation (or order of cards) that takes 159 steps of "topswopping moves" before it terminates in sorted order, i.e., (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17). (End)

Comment from Moritz Franckenstein, Apr 16 2011: (Start)

n=18 -> 191

6 14 9 2 15 8 1 3 4 12 18 5 10 13 16 17 11 7

n=19 -> 207

2 3 7 8 4 19 10 15 17 6 1 11 5 18 12 9 13 14 16

3 7 2 8 4 19 10 15 17 6 1 11 5 18 12 9 13 14 16

n=20 -> 231

5 20 6 3 2 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4

3 20 5 6 2 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4

5 20 2 6 3 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4 (End)

References

D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.

Links

Table of n, a(n) for n=1..20.

Linda Morales and Hal Sudborough, A quadratic lower bound for Topswops, Theoretical Computer Science, Volume 411, Issues 44-46, 25 October 2010, Pages 3965-3970.

Prog

(Python)
def a(n): # see A000375 for ts
  return max(ts(d, var=2) for d in P(range(1, n+1)))
print([a(n) for n in range(1, 11)]) # Michael S. Branicky, Dec 11 2020

Crossrefs

Cf. A000375, A174498.

Sequence in context: A176099 A160790 A173726 * A000375 A244488 A365068

Adjacent sequences: A000373 A000374 A000375 * A000377 A000378 A000379

Keyword

nonn,hard,nice,more

Author

Bill Blewett, Mike Toepke [ mtoepke(AT)microsoft.com ]

Extensions

a(14)-a(15) from James Kilfiger (mapdn(AT)csv.warwick.ac.uk), Jul 1997

a(16)-a(17) from William Rex Marshall, Mar 28 2001

Definition clarified by Franklin T. Adams-Watters, Jan 24 2007

a(18) from Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010

a(1)=0 prepended by Max Alekseyev, Nov 18 2010

a(19) from Moritz Franckenstein, Dec 14 2010

a(20) from Moritz Franckenstein, Apr 16 2011

Status

approved