

A000375


Topswops (1): start by shuffling n cards labeled 1..n. If top card is m, reverse order of top m cards, then repeat. a(n) is the maximal number of steps before top card is 1.


2



0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 65, 80, 101, 113, 139, 159
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Knuth's algorithm can be extended by considering unsorted large unmovable segments: xxx645, e.g. will never move 6, 4, or 5.  Quan T. Nguyen, William Fahle (waf013000(AT)utdallas.edu), Oct 12 2010
For n=17, there are two longestwinded permutations (or orders of cards) that take 159 steps of "topswopping moves" before the top card is 1. (8 15 17 13 9 4 6 3 2 12 16 14 11 5 10 1 7) terminates at (1 6 2 4 9 3 7 8 5 10 11 12 13 14 15 16 17), and (2 10 15 11 7 14 5 16 6 4 17 13 1 3 8 9 12) terminates in sorted order, i.e., (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17).  Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010
Lower bounds for the next terms are a(18)>=191, a(19)>=221, a(20)>=249, a(21)>=282, a(22)>=335, a(23)>=382.  Hugo Pfoertner, May 21 2011; updated Oct 08 2016


REFERENCES

Martin Gardner, Time Travel and Other Mathematical Bewilderments (Freeman, 1988), Chapter 6 [based on a column that originally appeared in Scientific American, November 1974].
M. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see p. 115117.
D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107109.


LINKS

Table of n, a(n) for n=1..17.
Kenneth Anderson and Duane Rettig, Performing Lisp Analysis of the FANNKUCH Benchmark
David Berman, M. S. Klamkin and D. E. Knuth, Problem 7617. A reverse card shuffle, SIAM Review 19 (1977), 739741.
Brent Fulgham, fannkuchredux benchmark, The Computer Language Benchmarks Game
D. E. Knuth, Downloadable programs
Klaus Nagel, Vau, Java applet for Topswops visualization.  Hugo Pfoertner, May 21 2011
Andy Pepperdine, Topswops, Mathematical Gazette 73 (1989), 131133.


EXAMPLE

From R. K. Guy, Jan 24 2007: (Start)
With 4 cards there are just two permutations which require 4 flips:
3142 > 4132 > 2314 > 3214 > 1234
2413 > 4213 > 3124 > 2134 > 1234
In these cases the deck finishes up sorted. But this is not always the case  see A000376. (End)


MATHEMATICA

Table[Max@ Map[Length@ NestWhileList[Flatten@{Reverse@Take[#, First@ #], Take[#, (Length@ #  First@ #)]} &, #, First@ # != 1 &]  1 &, Permutations@ Range@ n], {n, 8}] (* Michael De Vlieger, Oct 08 2016 *)


PROG

(PARI) a(n)=my(s, t, v); for(i=1, n!, v=numtoperm(n, i); t=0; while(v[1]>1, v=if(v[1]<n, concat(Vecrev(v[1..v[1]]), v[v[1]+1..n]), Vecrev(v)); t++); s=max(s, t)); s \\ Charles R Greathouse IV, Oct 14 2013


CROSSREFS

Cf. A000376 (a variation), A123398 (number of solutions).
Sequence in context: A160790 A173726 A000376 * A244488 A131752 A062365
Adjacent sequences: A000372 A000373 A000374 * A000376 A000377 A000378


KEYWORD

nonn,hard,nice,more


AUTHOR

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


EXTENSIONS

One more term from James Kilfiger (mapdn(AT)csv.warwick.ac.uk), July 1997
113 from William Rex Marshall, Mar 27 2001
139 from Don Knuth, Aug 25 2001
Added one new term by improved branch and bound using various new insights.  Quan T. Nguyen, William Fahle (waf013000(AT)utdallas.edu), Oct 12 2010


STATUS

approved



