|
%I #53 Sep 13 2023 08:28:01
%S 0,1,2,4,7,10,16,22,30,38,51,63,80,101,112,130,159,191,207,231
%N 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.
%C See also A000375, which is the main entry for this problem.
%C Comments from _Joshua Zucker_, Jan 24 2007: (Start)
%C 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:
%C The examples below use 0 through n-1 instead of 1 through n.
%C ((#(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))
%C (#(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))
%C (#(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))
%C (#(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)))
%C (#(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))
%C 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:
%C #(9 10 6 0 2 7 1 8 11 5 3 4)
%C #(9 10 6 0 1 2 7 8 11 5 3 4)
%C #(7 8 11 5 0 6 10 9 2 1 3 4)
%C #(5 0 1 7 10 3 11 8 9 6 2 4)
%C But 65 is attainable if you don't assume it ends up sorted. (End)
%C Comment from Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010: (Start)
%C (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).
%C 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)
%C Comment from _Moritz Franckenstein_, Apr 16 2011: (Start)
%C n=18 -> 191
%C 6 14 9 2 15 8 1 3 4 12 18 5 10 13 16 17 11 7
%C n=19 -> 207
%C 2 3 7 8 4 19 10 15 17 6 1 11 5 18 12 9 13 14 16
%C 3 7 2 8 4 19 10 15 17 6 1 11 5 18 12 9 13 14 16
%C n=20 -> 231
%C 5 20 6 3 2 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4
%C 3 20 5 6 2 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4
%C 5 20 2 6 3 15 10 1 16 9 18 14 19 7 12 17 8 11 13 4 (End)
%D D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.
%H Linda Morales and Hal Sudborough, <a href="https://doi.org/10.1016/j.tcs.2010.08.011">A quadratic lower bound for Topswops</a>, Theoretical Computer Science, Volume 411, Issues 44-46, 25 October 2010, Pages 3965-3970.
%o (Python)
%o def a(n): # see A000375 for ts
%o return max(ts(d, var=2) for d in P(range(1, n+1)))
%o print([a(n) for n in range(1, 11)]) # _Michael S. Branicky_, Dec 11 2020
%Y Cf. A000375, A174498.
%K nonn,hard,nice,more
%O 1,3
%A _Bill Blewett_, Mike Toepke [ mtoepke(AT)microsoft.com ]
%E a(14)-a(15) from James Kilfiger (mapdn(AT)csv.warwick.ac.uk), Jul 1997
%E a(16)-a(17) from _William Rex Marshall_, Mar 28 2001
%E Definition clarified by _Franklin T. Adams-Watters_, Jan 24 2007
%E a(18) added by Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010
%E a(1)=0 prepended by _Max Alekseyev_, Nov 18 2010
%E a(19) added by _Moritz Franckenstein_, Dec 14 2010
%E a(20) added by _Moritz Franckenstein_, Apr 16 2011
| 