|
| |
|
|
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 "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
|
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.
Andy Pepperdine, Topswops, Mathematical Gazette 73 (1989), 131-133.
|
|
|
EXAMPLE
|
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)))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard,nice,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
