This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 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 (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. 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. Brent Fulgham, fannkuch-redux benchmark, The Computer Language Benchmarks Game D. E. Knuth, Downloadable programs 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.