The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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]

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 31 16:08 EDT 2023. Contains 361668 sequences. (Running on oeis4.)