|
| |
|
|
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; 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 [From Quan T. Nguyen, William Fahle (waf013000(AT)utdallas.edu), Oct 12 2010]
Contribution from Quan T. Nguyen, William Fahle (tuongquan.nguyen(AT)utdallas.edu), Oct 21 2010: (Start)
For n=17, there are two longest-winded 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) (End)
Lower bounds for the next terms are a(18)>=191, a(19)>=221, a(20)>=249, a(21)>=282, a(22)>=312, a(23)>=382. [Hugo Pfoertner, May 21 2011]
|
|
|
REFERENCES
| David Berman, M. S. Klamkin and D. E. Knuth, Problem 76-17*, A reverse card shuffle, SIAM Review 19 (1977), 739-741.
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. 115-117.
D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.
Andy Pepperdine, Topswops, Mathematical Gazette 73 (1989), 131-133.
|
|
|
LINKS
| D. E. Knuth, Downloadable programs
Klaus Nagel, Vau, Java applet for Topswops visualization
|
|
|
EXAMPLE
| Comment from R. K. Guy, Jan 24 2007: 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.
|
|
|
CROSSREFS
| Cf. A000376 (a variation), A123398 (number of solutions).
Sequence in context: A160790 A173726 A000376 * A131752 A062365 A049630
Adjacent sequences: A000372 A000373 A000374 * A000376 A000377 A000378
|
|
|
KEYWORD
| nonn,hard,nice,more
|
|
|
AUTHOR
| Bill Blewett [billble(AT)microsoft.com] 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 (w.r.marshall(AT)actrix.co.nz), Mar 27 2001
139 from D. E. 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
Comment with lower bounds for a(18)-a(23) and link to Klaus Nagel's Java applet from Hugo Pfoertner (hugo(AT)pfoertner.org), May 21 2011
|
| |
|
|
