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.

0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 65, 80, 101, 113, 139, 159, 191, 221

Offset: 1

Author

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

Keywords

• nonn
• hard
• nice
• more

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

Examples

			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)
		

References

• 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. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.

Links

• 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. Also published in: M. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see p. 115-117.
• 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.
• L. Morales and H. Sudborough, A quadratic lower bound for Topswops, Theor. Comp. Sci 411 (2010) 3965-3970.
• Andy Pepperdine, Topswops, Mathematical Gazette 73 (1989), 131-133.

Crossrefs

Cf. A000376 (a variation), A123398 (number of solutions).

Programs

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 *)

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]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

Extensions

One more term from James Kilfiger, Jul 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