A174498
Topswops (2): number of permutations of cards achieving A000376(n).
Original entry on oeis.org
1, 1, 2, 2, 1, 4, 2, 1, 1, 1, 1, 4, 1, 4, 2, 2, 1, 1, 2, 3
Offset: 1
- D. E. Knuth, TAOCP, Section 7.2.1.2, Problems 107-109.
a(20)=3 by Moritz Franckenstein, Apr 16 2011.
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.
Original entry on oeis.org
0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 65, 80, 101, 113, 139, 159, 191, 221
Offset: 1
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)
- 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.
- 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.
-
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 *)
-
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
-
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
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
Showing 1-2 of 2 results.
Comments