|
Search: id:A000375
|
|
|
| A000375 |
|
Topswops (1): shuffle n cards labeled 1..n. If top card is m, reverse order of top m cards. a(n) is the maximal number of steps before top card is 1. |
|
+0
3
|
|
| 0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 65, 80, 101, 113, 139
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
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
|
|
EXAMPLE
|
Comment from R. K. Guy, Jan 24 2007: With 4 cards there are just two perms 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).
Adjacent sequences: A000372 A000373 A000374 this_sequence A000376 A000377 A000378
Sequence in context: A024668 A160790 A000376 this_sequence A131752 A062365 A049630
|
|
KEYWORD
|
nonn,hard,nice
|
|
AUTHOR
|
Bill Blewett [ billble(AT)microsoft.com ], Mike Toepke [ mtoepke(AT)microsoft.com ]
|
|
EXTENSIONS
|
One more term from James Kilfiger (mapdn(AT)csv.warwick.ac.uk) 7/97. 113 from William Rex Marshall (w.r.marshall(AT)actrix.co.nz), Mar 27 2001. 139 from D. E. Knuth, Aug 25, 2001
|
|
|
Search completed in 0.002 seconds
|
