%I A000376
%S A000376 1,2,4,7,10,16,22,30,38,51,63,80,101,112,130,159
%N A000376 Topswops (2): shuffle n cards labeled 1..n. If top card is m, reverse 
               order of top m cards. Repeat until 1 gets to 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 A000376 See also A000375, which is the main entry for this problem.
%C A000376 Comments from Joshua Zucker (joshua.zucker(AT)gmail.com), Jan 24 2007: 
               (Start)
%C A000376 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 A000376 The examples below use 0 through n-1 instead of 1 through n.
%C A000376 ((#(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 A000376 (#(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 A000376 (#(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 A000376 (#(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 A000376 (#(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 A000376 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 A000376 #(9 10 6 0 2 7 1 8 11 5 3 4)
%C A000376 #(9 10 6 0 1 2 7 8 11 5 3 4)
%C A000376 #(7 8 11 5 0 6 10 9 2 1 3 4)
%C A000376 #(5 0 1 7 10 3 11 8 9 6 2 4)
%C A000376 But 65 is attainable if you don't assume it ends up sorted. (End)
%D A000376 D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.
%Y A000376 Cf. A000375.
%Y A000376 Sequence in context: A049640 A024668 A160790 this_sequence A000375 A131752 
               A062365
%Y A000376 Adjacent sequences: A000373 A000374 A000375 this_sequence A000377 A000378 
               A000379
%K A000376 nonn,hard,nice
%O A000376 2,2
%A A000376 Bill Blewett [ billble(AT)microsoft.com ], Mike Toepke [ mtoepke(AT)microsoft.com 
               ]
%E A000376 Two more terms from James Kilfiger (mapdn(AT)csv.warwick.ac.uk) 7/97. 
               130 and 159 from William Rex Marshall (w.r.marshall(AT)actrix.co.nz), 
               Mar 28 2001.
%E A000376 Definition clarified by Franklin T. Adams-Watters, Jan 24 2007