|
| |
|
|
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, 191, 221
(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 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). - 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. 115-117.
D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.
L. Morales, H. Sudborough, A quadratic lower bound for Topswops, Theor. Comp. Sci 411 (2010) 3965-3970 doi:10.1016/j.tcs.2010.08.011
|
|
|
LINKS
|
Table of n, a(n) for n=1..19.
Kenneth Anderson and Duane Rettig, Performing Lisp Analysis of the FANNKUCH Benchmark
David Berman, M. S. Klamkin and D. E. Knuth, Problem 76-17. A reverse card shuffle, SIAM Review 19 (1977), 739-741.
Zhang Desheng, The Topswop Forest, bachelor thesis, Linnaeus Univ. (Sweden, 2021). Mentions the terms of this sequence.
Brent Fulgham, fannkuch-redux benchmark, The Computer Language Benchmarks Game
Kento Kimura, Atsuki Takahashi, Tetsuya Araki, and Kazuyuki Amano, Maximum Number of Steps of Topswops on 18 and 19 Cards, arXiv:2103.08346 [cs.DM], 2021.
Kento Kimura, kimurakento / tswops, 2021.
D. E. Knuth, Downloadable programs
Yuichi Komano and Takaaki Mizuki, Physical Zero-Knowledge Proof Protocol for Topswops, Int'l Conf. Info. Sec. Practice and Experience (ISPEC 2022) Lecture Notes in Comp. Sci. book series (LNCS Vol. 13620) Springer, Cham, 537-553.
Klaus Nagel, Vau, Java applet for Topswops visualization. - Hugo Pfoertner, May 21 2011
Andy Pepperdine, Topswops, Mathematical Gazette 73 (1989), 131-133.
|
|
|
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
(Python)
from itertools import permutations as P
def ts(d, var=1): # algorithm VARiation
s, m = 0, d[0]
while m != 1:
d = (d[:m])[::-1] + d[m:]
s, m = s+1, d[0]
if var==2: return s*(list(d)==sorted(d))
return s
def a(n):
return max(ts(d) for d in P(range(1, n+1)))
print([a(n) for n in range(1, 11)]) # Michael S. Branicky, Dec 11 2020
|
|
|
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
a(18)-a(19) from Kimura et al. added by Andrey Zabolotskiy, Mar 24 2021
|
|
|
STATUS
|
approved
|
| |
|
|
