login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000376 Topswops (2): start by shuffling 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. 3
0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 63, 80, 101, 112, 130, 159, 191, 207, 231 (list; graph; refs; listen; history; text; internal format)
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)

(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) [From Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010]

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) [From Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010]

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

REFERENCES

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

LINKS

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

CROSSREFS

Cf. A000375, A174498.

Sequence in context: A176099 A160790 A173726 * A000375 A244488 A131752

Adjacent sequences:  A000373 A000374 A000375 * A000377 A000378 A000379

KEYWORD

nonn,hard,nice,more

AUTHOR

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

EXTENSIONS

Two more terms from James Kilfiger (mapdn(AT)csv.warwick.ac.uk) 7/97.

130 and 159 from William Rex Marshall, Mar 28 2001.

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

a(18)=191 added by 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)=207 added by Moritz Franckenstein, Dec 14 2010

a(20)=231 added by Moritz Franckenstein, Apr 16 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 22 08:57 EST 2017. Contains 295076 sequences.