|
%I #85 Jul 03 2023 19:49:20
%S 0,1,2,4,7,10,16,22,30,38,51,65,80,101,113,139,159,191,221
%N 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.
%C 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
%C 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
%C 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
%D Martin Gardner, Time Travel and Other Mathematical Bewilderments (Freeman, 1988), Chapter 6 "Combinatorial Card Problems" [based on a column that originally appeared in Scientific American, November 1974].
%D D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.
%H Kenneth Anderson and Duane Rettig, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.5124">Performing Lisp Analysis of the FANNKUCH Benchmark</a>
%H David Berman, M. S. Klamkin and D. E. Knuth, <a href="http://www.jstor.org/stable/2030263">Problem 76-17. A reverse card shuffle</a>, SIAM Review 19 (1977), 739-741. Also published in: M. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see p. 115-117.
%H Zhang Desheng, <a href="https://www.diva-portal.org/smash/record.jsf?pid=diva2%3A1563902">The Topswop Forest</a>, bachelor thesis, Linnaeus Univ. (Sweden, 2021). Mentions the terms of this sequence.
%H Brent Fulgham, <a href="https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/fannkuchredux.html">fannkuch-redux benchmark</a>, The Computer Language Benchmarks Game
%H Kento Kimura, Atsuki Takahashi, Tetsuya Araki, and Kazuyuki Amano, <a href="https://arxiv.org/abs/2103.08346">Maximum Number of Steps of Topswops on 18 and 19 Cards</a>, arXiv:2103.08346 [cs.DM], 2021.
%H Kento Kimura, <a href="https://gitlab.com/kkimura/tswops">kimurakento / tswops</a>, 2021.
%H D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/programs.html">Downloadable programs</a>
%H Yuichi Komano and Takaaki Mizuki, <a href="https://doi.org/10.1007/978-3-031-21280-2_30">Physical Zero-Knowledge Proof Protocol for Topswops</a>, Int'l Conf. Info. Sec. Practice and Experience (ISPEC 2022) Lecture Notes in Comp. Sci. book series (LNCS Vol. 13620) Springer, Cham, 537-553.
%H L. Morales and H. Sudborough, <a href="https://doi.org/10.1016/j.tcs.2010.08.011">A quadratic lower bound for Topswops</a>, Theor. Comp. Sci 411 (2010) 3965-3970.
%H Andy Pepperdine, <a href="http://www.jstor.org/stable/3619674">Topswops</a>, Mathematical Gazette 73 (1989), 131-133.
%e From _R. K. Guy_, Jan 24 2007: (Start)
%e With 4 cards there are just two permutations which require 4 flips:
%e 3142 --> 4132 --> 2314 --> 3214 --> 1234
%e 2413 --> 4213 --> 3124 --> 2134 --> 1234
%e In these cases the deck finishes up sorted. But this is not always the case - see A000376. (End)
%t 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 *)
%o (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
%o (Python)
%o from itertools import permutations as P
%o def ts(d, var=1): # algorithm VARiation
%o s, m = 0, d[0]
%o while m != 1:
%o d = (d[:m])[::-1] + d[m:]
%o s, m = s+1, d[0]
%o if var==2: return s*(list(d)==sorted(d))
%o return s
%o def a(n):
%o return max(ts(d) for d in P(range(1, n+1)))
%o print([a(n) for n in range(1, 11)]) # _Michael S. Branicky_, Dec 11 2020
%Y Cf. A000376 (a variation), A123398 (number of solutions).
%K nonn,hard,nice,more
%O 1,3
%A _Bill Blewett_ and Mike Toepke [mtoepke(AT)microsoft.com]
%E One more term from _James Kilfiger_, July 1997
%E 113 from _William Rex Marshall_, Mar 27 2001
%E 139 from _Don Knuth_, Aug 25 2001
%E 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
%E a(18)-a(19) from Kimura et al. added by _Andrey Zabolotskiy_, Mar 24 2021
|
