1131:
1070:
25:
2779:. The optimal values are, however, still unknown. There have been several attempts to find the optimal values, for example by A. Pepperdine. For rows with 19 or fewer numbers, the exact solution is known. Larger rows only have lower bounds, which is shown on the right.
854:
102:
in 1973. Contrary to other games and problems introduced by Conway, these problems have not received much attention from the scientific community. Two famous mathematicians who have contributed to the problem are
49:
709:
2702:
2512:
1187:. The data points in the graph are only some permutated rows, and are lower bounds of the real value. The upper bound is again very loose, whereas the lower bound is relatively tight.
115:
1631:
2028:
1365:
2580:
3078:
cards of the pile are swapped. Unless the bottom card is the highest card in the pile, nothing happens. This makes the problem uninteresting due to the limited behaviour.
2397:
1045:
2722:
2081:
1065:
1004:
2116:
2061:
1905:
1856:
1530:
1501:
515:
255:
2541:
2233:
1433:
2260:
2143:
1772:
1658:
1251:
2753:
1219:
1181:
1120:
482:
449:
2635:
2452:
2364:
2335:
2198:
1960:
1807:
1740:
1468:
1398:
955:
142:
3146:
3117:
3076:
3047:
2982:
2953:
2777:
2609:
2426:
2309:
2280:
2163:
1980:
1934:
1698:
1678:
1579:
1550:
1312:
1292:
1152:
1091:
984:
920:
893:, leaves the Wilf number unchanged. The remaining numbers at 'the correct position' will in general not be at 'the correct position' anymore. Nevertheless, the
891:
617:
597:
577:
548:
385:
362:
336:
304:
199:
179:
714:
711:. We are specifically interested in numbers which are at 'the correct position'. These are: 2, 5, 9, 10, 12. We define the Wilf number as
3373:
3364:
3280:
3249:
3224:
3407:
1047:. By refining the proof, the given upper bound can be proven to be a real upper bound for the number of iterations.
622:
39:
2640:
2457:
2992:. As an example, we consider the row 2,1,3,4. By applying the algorithm, the following sequence is obtained:
2926:, where the same playing cards are used. In this problem, the first card of the pile is shown (and has value
1008:
The maximal Wilf number is found when each number is at the correct position. So the maximal Wilf number is
1584:
3402:
864:
Proof: We perform one iteration of the algorithm. Every number at 'the correct position' and larger than
1985:
1322:
3347:
2984:
cards of the pile, change the order and place them back on the bottom of the pile (which contrasts
2546:
418:
Which initial configuration leads to the maximum number of 'swops' before the algorithm terminates?
422:
In literature there are some attempts to find lower and upper bounds for the number of iterations
2369:
3272:
3266:
3216:
3210:
1371:
1123:
1011:
2707:
2066:
1050:
989:
3332:
2088:
2033:
1861:
1812:
1509:
1473:
487:
204:
89:
3323:
2726:
Besides these results, Morales and
Sudborough have recently proven that the lower bound for
2520:
2203:
1403:
2238:
2121:
1745:
1636:
1224:
986:, the total Wilf number always increases (with at least 1 per iteration of the algorithm).
2729:
1195:
1157:
1096:
458:
425:
8:
2614:
2431:
2343:
2314:
2168:
1939:
1777:
1703:
1438:
1377:
925:
121:
3313:
3122:
3093:
3052:
3023:
2958:
2929:
2762:
2756:
2585:
2402:
2285:
2265:
2148:
1965:
1910:
1683:
1663:
1555:
1535:
1297:
1268:
1184:
1137:
1076:
960:
896:
867:
602:
582:
553:
524:
370:
347:
312:
280:
184:
164:
99:
3276:
3245:
3220:
1262:
158:
3305:
3184:
1254:
35:
3242:
The Art of computer programming: Volume 4, Fascicle 2A: Generating all n-tuples
3169:
2989:
104:
93:
54:
3189:
3396:
154:
96:
1130:
1069:
108:
860:
Claim: after each iteration of the algorithm, the Wilf number increases.
849:{\displaystyle 2^{(2-1)}+2^{(5-1)}+2^{(9-1)}+2^{(10-1)}+2^{(12-1)}=2833}
3317:
3020:
In this variant, the bottom card of the pile is taken (and again named
922:'s number is at the correct position. And since the sum of the first
270:
161:
is used. This is mathematically equivalent to a row of integers from
157:. Since the numerical values of the deck are only relevant, only one
44:
3309:
3382:
1126:. The upper bound is loose, whereas the lower bound is quite tight.
3387:
3383:
Rosetta code: Computing
Topswops in multiple programming languages
2988:, where the cards are placed at the top). This problem allows for
114:
2911:
391:
problem is occasionally named differently, with naming including
3388:
Topswops competition to compute the maximal number of iterations
24:
3268:
Problems in
Applied Mathematics: Selections from SIAM review
3377:
3368:
1633:. Suppose that the largest value of these values, which is
3324:
https://www.pepsplace.org.uk/Trivia/Topswops/Topswops.pdf
957:
Wilf numbers is always smaller than the Wilf number of
1265:: Suppose that during the algorithm, the first number
367:
The final configuration of the row always starts with
153:
In each variant of the problem, Conway uses a deck of
3125:
3096:
3055:
3026:
2961:
2932:
2765:
2732:
2710:
2643:
2617:
2588:
2549:
2523:
2460:
2434:
2405:
2372:
2346:
2317:
2288:
2268:
2241:
2206:
2171:
2151:
2124:
2091:
2069:
2036:
1988:
1968:
1942:
1913:
1864:
1815:
1780:
1748:
1706:
1686:
1666:
1639:
1587:
1558:
1538:
1512:
1476:
1441:
1406:
1380:
1325:
1300:
1271:
1227:
1198:
1160:
1140:
1099:
1079:
1053:
1014:
992:
963:
928:
899:
870:
717:
625:
605:
585:
556:
527:
490:
461:
428:
373:
350:
315:
283:
207:
187:
167:
124:
2637:distinct values. Using the claim, it follows that
414:The problem formulated by Conway is the following:
3140:
3111:
3090:where the bottom card of the pile is taken (again
3070:
3041:
2976:
2947:
2771:
2747:
2716:
2696:
2629:
2603:
2574:
2535:
2506:
2446:
2420:
2391:
2358:
2329:
2303:
2274:
2254:
2227:
2192:
2157:
2137:
2110:
2075:
2055:
2022:
1974:
1954:
1928:
1899:
1850:
1801:
1766:
1734:
1692:
1672:
1652:
1625:
1573:
1544:
1524:
1495:
1462:
1427:
1392:
1359:
1306:
1286:
1245:
1213:
1175:
1146:
1114:
1085:
1059:
1039:
998:
978:
949:
914:
885:
848:
703:
611:
591:
571:
542:
509:
476:
443:
379:
356:
330:
298:
249:
193:
173:
136:
3322:A renewed version of the article can be found on
3167:
521:Proof by Herbert S. Wilf: Consider a permutation
3394:
3295:
3212:Time Travel and Other Mathematical Bewilderments
341:Swap these cards and place them back on the pile
277:Consider the first card from the pile (which is
144:numbers. The algorithm ends after 7 iterations.
2235:. During the algorithm, we are sure that both
1858:. The remaining iterations will always retain
3289:
3215:. New York: W. H. Freeman & Co. pp.
3204:
3202:
3200:
3163:
3161:
1581:takes on, are ordered and can be written as:
704:{\displaystyle 7,2,11,8,5,13,6,1,9,10,3,12,4}
344:Repeat step 1, 2 and 3 until the top card is
3012:whereafter the original row is found again.
2697:{\displaystyle f(N)\leq F_{k}+r\leq F_{k+1}}
1400:, the algorithm directly terminates, hence,
16:Mathematical problems devised by John Conway
3296:Pepperdine, Andy (1989). "73.23 Topswops".
3258:
3197:
3158:
2910:It is yet unknown whether this problem is
3188:
201:. A shuffled pile of cards is written as
3378:page 376 (topswops which ends up sorted)
3244:. Addison-Wesley. pp. 74, 119–120.
3233:
3168:Morales, Linda; Sudborough, Hal (2010).
2507:{\displaystyle f(N)\leq r+1\leq F_{k+1}}
1660:, occurs for the first time at position
1134:Topswops: the expected relation between
1129:
1068:
113:
3264:
3208:
3395:
3170:"A quadratic lower bound for Topswops"
3239:
1626:{\displaystyle d_{1}<...<d_{k}}
2454:distinct values. So it follows that
18:
13:
14:
3419:
3358:
2023:{\displaystyle f(N)-r\leq F_{k}}
1360:{\displaystyle f(N)\leq F_{k+1}}
23:
3119:). In this variant, the bottom
1073:Topswops: the relation between
3135:
3129:
3106:
3100:
3065:
3059:
3036:
3030:
2971:
2965:
2942:
2936:
2742:
2736:
2653:
2647:
2598:
2592:
2470:
2464:
2415:
2409:
2298:
2292:
2216:
2210:
2200:and the algorithm terminates;
2181:
2175:
1998:
1992:
1923:
1917:
1881:
1868:
1832:
1819:
1790:
1784:
1761:
1749:
1729:
1716:
1568:
1562:
1451:
1445:
1416:
1410:
1335:
1329:
1281:
1275:
1240:
1228:
1208:
1202:
1170:
1164:
1109:
1103:
973:
967:
938:
932:
909:
903:
880:
874:
835:
823:
810:
798:
785:
773:
760:
748:
735:
723:
566:
560:
537:
531:
471:
465:
438:
432:
325:
319:
293:
287:
244:
238:
217:
211:
148:
1:
3209:Gardner, Martin (1987). "6".
3151:
2575:{\displaystyle r\leq F_{k-1}}
1370:Proof: We prove the claim by
619:. As an example, we consider
393:deterministic pancake problem
3298:The Mathematical Association
3177:Theoretical Computer Science
2847:maximal number of iterations
2282:have never been at position
1962:values. Using induction for
92:devised and analysed by the
7:
3265:Klamkin, Murray S. (1990).
3081:
3015:
2917:
2704:. This proves the theorem.
2392:{\displaystyle r\leq F_{k}}
260:
10:
3424:
2085:Suppose we would exchange
3240:Knuth, Donald E. (2002).
3190:10.1016/j.tcs.2010.08.011
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2808:
2805:
2802:
2799:
2796:
2793:
2790:
2787:
1700:of the algorithm. Denote
1040:{\displaystyle 2^{N+1}-1}
3408:Recreational mathematics
2717:{\displaystyle \square }
2076:{\displaystyle \square }
1936:can now take on at most
1185:double logarithmic graph
1060:{\displaystyle \square }
999:{\displaystyle \square }
118:A Topswops example with
2111:{\displaystyle d_{1}=1}
2056:{\displaystyle d_{1}=1}
1900:{\displaystyle A=d_{k}}
1851:{\displaystyle A=d_{k}}
1774:'th iteration, we know
1525:{\displaystyle k\geq 2}
1496:{\displaystyle F_{2}=1}
510:{\displaystyle 2^{N-1}}
250:{\displaystyle A,...,A}
38:, as no other articles
3142:
3113:
3072:
3043:
2978:
2949:
2773:
2749:
2718:
2698:
2631:
2605:
2576:
2537:
2536:{\displaystyle t>1}
2508:
2448:
2422:
2393:
2360:
2331:
2305:
2276:
2256:
2229:
2228:{\displaystyle f(N)=r}
2194:
2159:
2139:
2112:
2077:
2057:
2024:
1976:
1956:
1930:
1901:
1852:
1803:
1768:
1736:
1694:
1674:
1654:
1627:
1575:
1546:
1526:
1497:
1464:
1429:
1428:{\displaystyle f(N)=0}
1394:
1372:mathematical induction
1361:
1308:
1288:
1247:
1215:
1188:
1177:
1148:
1127:
1124:semi-logarithmic graph
1116:
1087:
1061:
1041:
1000:
980:
951:
916:
887:
850:
705:
613:
593:
573:
544:
511:
478:
445:
381:
358:
332:
300:
251:
195:
175:
145:
138:
3143:
3114:
3086:The final variant is
3073:
3044:
2979:
2950:
2922:A similar problem is
2774:
2750:
2719:
2699:
2632:
2606:
2577:
2538:
2509:
2449:
2423:
2394:
2361:
2332:
2306:
2277:
2257:
2255:{\displaystyle d_{k}}
2230:
2195:
2160:
2140:
2138:{\displaystyle d_{k}}
2113:
2078:
2058:
2025:
1977:
1957:
1931:
1902:
1853:
1804:
1769:
1767:{\displaystyle (r+1)}
1737:
1695:
1675:
1655:
1653:{\displaystyle d_{k}}
1628:
1576:
1547:
1527:
1503:the claim is proven.
1498:
1465:
1430:
1395:
1362:
1309:
1289:
1248:
1246:{\displaystyle (N+1)}
1216:
1178:
1149:
1133:
1117:
1088:
1072:
1062:
1042:
1001:
981:
952:
917:
888:
851:
706:
614:
594:
574:
545:
512:
479:
446:
382:
359:
333:
301:
252:
196:
176:
139:
117:
90:mathematical problems
3183:(44–46): 3965–3970.
3123:
3094:
3053:
3024:
2959:
2930:
2763:
2748:{\displaystyle f(N)}
2730:
2708:
2641:
2615:
2586:
2547:
2521:
2458:
2432:
2403:
2370:
2344:
2315:
2286:
2266:
2239:
2204:
2169:
2149:
2122:
2089:
2067:
2034:
1986:
1966:
1940:
1911:
1862:
1813:
1778:
1746:
1704:
1684:
1664:
1637:
1585:
1556:
1536:
1510:
1474:
1439:
1404:
1378:
1323:
1298:
1269:
1225:
1214:{\displaystyle f(N)}
1196:
1176:{\displaystyle f(N)}
1158:
1138:
1115:{\displaystyle f(N)}
1097:
1077:
1051:
1012:
990:
961:
926:
897:
868:
715:
623:
603:
583:
554:
525:
488:
477:{\displaystyle f(N)}
459:
444:{\displaystyle f(N)}
426:
405:reverse card shuffle
371:
348:
313:
281:
205:
185:
165:
122:
3369:page 375 (topswops)
3148:cards are swapped.
2630:{\displaystyle k-2}
2447:{\displaystyle k-1}
2359:{\displaystyle t=1}
2330:{\displaystyle t=1}
2193:{\displaystyle A=1}
1955:{\displaystyle k-1}
1802:{\displaystyle A=t}
1735:{\displaystyle t=A}
1463:{\displaystyle A=1}
1393:{\displaystyle k=1}
950:{\displaystyle A-1}
338:cards from the pile
137:{\displaystyle N=5}
3403:John Horton Conway
3138:
3109:
3068:
3049:). Then the first
3039:
2974:
2955:). Take the first
2945:
2769:
2757:quadratic function
2745:
2714:
2694:
2627:
2601:
2572:
2533:
2504:
2444:
2418:
2389:
2356:
2327:
2301:
2272:
2252:
2225:
2190:
2155:
2135:
2108:
2073:
2053:
2020:
1982:, it follows that
1972:
1952:
1926:
1897:
1848:
1799:
1764:
1732:
1690:
1670:
1650:
1623:
1571:
1542:
1522:
1493:
1460:
1425:
1390:
1357:
1304:
1294:takes on in total
1284:
1243:
1221:is bounded by the
1211:
1189:
1173:
1144:
1128:
1112:
1083:
1057:
1037:
996:
976:
947:
912:
883:
846:
701:
609:
589:
569:
540:
507:
474:
441:
377:
354:
328:
296:
247:
191:
171:
146:
134:
76:(and the variants
57:for suggestions.
47:to this page from
3340:External link in
3271:. SIAM. pp.
3141:{\displaystyle A}
3112:{\displaystyle A}
3071:{\displaystyle A}
3042:{\displaystyle A}
2977:{\displaystyle A}
2948:{\displaystyle A}
2908:
2907:
2772:{\displaystyle N}
2611:takes on at most
2604:{\displaystyle A}
2428:takes on at most
2421:{\displaystyle A}
2304:{\displaystyle A}
2275:{\displaystyle t}
2158:{\displaystyle r}
1975:{\displaystyle k}
1929:{\displaystyle A}
1693:{\displaystyle r}
1680:during iteration
1673:{\displaystyle 1}
1574:{\displaystyle A}
1545:{\displaystyle k}
1506:We now take some
1314:distinct values.
1307:{\displaystyle k}
1287:{\displaystyle A}
1263:Murray S. Klamkin
1147:{\displaystyle N}
1086:{\displaystyle N}
979:{\displaystyle A}
915:{\displaystyle A}
886:{\displaystyle A}
612:{\displaystyle N}
592:{\displaystyle 1}
572:{\displaystyle A}
543:{\displaystyle A}
380:{\displaystyle 1}
357:{\displaystyle 1}
331:{\displaystyle A}
299:{\displaystyle A}
194:{\displaystyle N}
174:{\displaystyle 1}
71:
70:
3415:
3352:
3351:
3345:
3344:
3338:
3336:
3328:
3304:(464): 131–133.
3293:
3287:
3286:
3262:
3256:
3255:
3237:
3231:
3230:
3206:
3195:
3194:
3192:
3174:
3165:
3147:
3145:
3144:
3139:
3118:
3116:
3115:
3110:
3077:
3075:
3074:
3069:
3048:
3046:
3045:
3040:
2983:
2981:
2980:
2975:
2954:
2952:
2951:
2946:
2782:
2781:
2778:
2776:
2775:
2770:
2754:
2752:
2751:
2746:
2723:
2721:
2720:
2715:
2703:
2701:
2700:
2695:
2693:
2692:
2668:
2667:
2636:
2634:
2633:
2628:
2610:
2608:
2607:
2602:
2581:
2579:
2578:
2573:
2571:
2570:
2542:
2540:
2539:
2534:
2513:
2511:
2510:
2505:
2503:
2502:
2453:
2451:
2450:
2445:
2427:
2425:
2424:
2419:
2398:
2396:
2395:
2390:
2388:
2387:
2365:
2363:
2362:
2357:
2336:
2334:
2333:
2328:
2310:
2308:
2307:
2302:
2281:
2279:
2278:
2273:
2261:
2259:
2258:
2253:
2251:
2250:
2234:
2232:
2231:
2226:
2199:
2197:
2196:
2191:
2164:
2162:
2161:
2156:
2144:
2142:
2141:
2136:
2134:
2133:
2117:
2115:
2114:
2109:
2101:
2100:
2082:
2080:
2079:
2074:
2062:
2060:
2059:
2054:
2046:
2045:
2029:
2027:
2026:
2021:
2019:
2018:
1981:
1979:
1978:
1973:
1961:
1959:
1958:
1953:
1935:
1933:
1932:
1927:
1906:
1904:
1903:
1898:
1896:
1895:
1880:
1879:
1857:
1855:
1854:
1849:
1847:
1846:
1831:
1830:
1808:
1806:
1805:
1800:
1773:
1771:
1770:
1765:
1741:
1739:
1738:
1733:
1728:
1727:
1699:
1697:
1696:
1691:
1679:
1677:
1676:
1671:
1659:
1657:
1656:
1651:
1649:
1648:
1632:
1630:
1629:
1624:
1622:
1621:
1597:
1596:
1580:
1578:
1577:
1572:
1551:
1549:
1548:
1543:
1531:
1529:
1528:
1523:
1502:
1500:
1499:
1494:
1486:
1485:
1469:
1467:
1466:
1461:
1434:
1432:
1431:
1426:
1399:
1397:
1396:
1391:
1366:
1364:
1363:
1358:
1356:
1355:
1313:
1311:
1310:
1305:
1293:
1291:
1290:
1285:
1255:Fibonacci number
1252:
1250:
1249:
1244:
1220:
1218:
1217:
1212:
1182:
1180:
1179:
1174:
1153:
1151:
1150:
1145:
1121:
1119:
1118:
1113:
1092:
1090:
1089:
1084:
1066:
1064:
1063:
1058:
1046:
1044:
1043:
1038:
1030:
1029:
1005:
1003:
1002:
997:
985:
983:
982:
977:
956:
954:
953:
948:
921:
919:
918:
913:
892:
890:
889:
884:
855:
853:
852:
847:
839:
838:
814:
813:
789:
788:
764:
763:
739:
738:
710:
708:
707:
702:
618:
616:
615:
610:
598:
596:
595:
590:
578:
576:
575:
570:
549:
547:
546:
541:
516:
514:
513:
508:
506:
505:
483:
481:
480:
475:
450:
448:
447:
442:
386:
384:
383:
378:
363:
361:
360:
355:
337:
335:
334:
329:
305:
303:
302:
297:
256:
254:
253:
248:
200:
198:
197:
192:
180:
178:
177:
172:
143:
141:
140:
135:
66:
63:
52:
50:related articles
27:
19:
3423:
3422:
3418:
3417:
3416:
3414:
3413:
3412:
3393:
3392:
3361:
3356:
3355:
3342:
3341:
3339:
3330:
3329:
3310:10.2307/3619674
3294:
3290:
3283:
3263:
3259:
3252:
3238:
3234:
3227:
3207:
3198:
3172:
3166:
3159:
3154:
3124:
3121:
3120:
3095:
3092:
3091:
3084:
3054:
3051:
3050:
3025:
3022:
3021:
3018:
2960:
2957:
2956:
2931:
2928:
2927:
2920:
2764:
2761:
2760:
2731:
2728:
2727:
2709:
2706:
2705:
2682:
2678:
2663:
2659:
2642:
2639:
2638:
2616:
2613:
2612:
2587:
2584:
2583:
2560:
2556:
2548:
2545:
2544:
2522:
2519:
2518:
2492:
2488:
2459:
2456:
2455:
2433:
2430:
2429:
2404:
2401:
2400:
2383:
2379:
2371:
2368:
2367:
2345:
2342:
2341:
2316:
2313:
2312:
2287:
2284:
2283:
2267:
2264:
2263:
2246:
2242:
2240:
2237:
2236:
2205:
2202:
2201:
2170:
2167:
2166:
2150:
2147:
2146:
2129:
2125:
2123:
2120:
2119:
2096:
2092:
2090:
2087:
2086:
2068:
2065:
2064:
2041:
2037:
2035:
2032:
2031:
2014:
2010:
1987:
1984:
1983:
1967:
1964:
1963:
1941:
1938:
1937:
1912:
1909:
1908:
1891:
1887:
1875:
1871:
1863:
1860:
1859:
1842:
1838:
1826:
1822:
1814:
1811:
1810:
1779:
1776:
1775:
1747:
1744:
1743:
1723:
1719:
1705:
1702:
1701:
1685:
1682:
1681:
1665:
1662:
1661:
1644:
1640:
1638:
1635:
1634:
1617:
1613:
1592:
1588:
1586:
1583:
1582:
1557:
1554:
1553:
1537:
1534:
1533:
1511:
1508:
1507:
1481:
1477:
1475:
1472:
1471:
1440:
1437:
1436:
1405:
1402:
1401:
1379:
1376:
1375:
1345:
1341:
1324:
1321:
1320:
1299:
1296:
1295:
1270:
1267:
1266:
1226:
1223:
1222:
1197:
1194:
1193:
1159:
1156:
1155:
1139:
1136:
1135:
1098:
1095:
1094:
1078:
1075:
1074:
1052:
1049:
1048:
1019:
1015:
1013:
1010:
1009:
991:
988:
987:
962:
959:
958:
927:
924:
923:
898:
895:
894:
869:
866:
865:
822:
818:
797:
793:
772:
768:
747:
743:
722:
718:
716:
713:
712:
624:
621:
620:
604:
601:
600:
584:
581:
580:
555:
552:
551:
526:
523:
522:
495:
491:
489:
486:
485:
460:
457:
456:
427:
424:
423:
372:
369:
368:
349:
346:
345:
314:
311:
310:
309:Take the first
282:
279:
278:
263:
206:
203:
202:
186:
183:
182:
166:
163:
162:
151:
123:
120:
119:
67:
61:
58:
48:
45:introduce links
28:
17:
12:
11:
5:
3421:
3411:
3410:
3405:
3391:
3390:
3385:
3380:
3371:
3360:
3359:External links
3357:
3354:
3353:
3288:
3282:978-0898712599
3281:
3257:
3251:978-0201853933
3250:
3232:
3226:978-0716719250
3225:
3196:
3156:
3155:
3153:
3150:
3137:
3134:
3131:
3128:
3108:
3105:
3102:
3099:
3083:
3080:
3067:
3064:
3061:
3058:
3038:
3035:
3032:
3029:
3017:
3014:
3010:
3009:
3006:
3003:
3000:
2997:
2990:infinite loops
2973:
2970:
2967:
2964:
2944:
2941:
2938:
2935:
2919:
2916:
2906:
2905:
2902:
2899:
2896:
2893:
2890:
2887:
2884:
2881:
2878:
2875:
2872:
2869:
2866:
2863:
2860:
2857:
2854:
2851:
2848:
2844:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2768:
2744:
2741:
2738:
2735:
2713:
2691:
2688:
2685:
2681:
2677:
2674:
2671:
2666:
2662:
2658:
2655:
2652:
2649:
2646:
2626:
2623:
2620:
2600:
2597:
2594:
2591:
2569:
2566:
2563:
2559:
2555:
2552:
2532:
2529:
2526:
2501:
2498:
2495:
2491:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2443:
2440:
2437:
2417:
2414:
2411:
2408:
2386:
2382:
2378:
2375:
2355:
2352:
2349:
2326:
2323:
2320:
2300:
2297:
2294:
2291:
2271:
2249:
2245:
2224:
2221:
2218:
2215:
2212:
2209:
2189:
2186:
2183:
2180:
2177:
2174:
2154:
2132:
2128:
2107:
2104:
2099:
2095:
2072:
2052:
2049:
2044:
2040:
2030:and also that
2017:
2013:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1971:
1951:
1948:
1945:
1925:
1922:
1919:
1916:
1894:
1890:
1886:
1883:
1878:
1874:
1870:
1867:
1845:
1841:
1837:
1834:
1829:
1825:
1821:
1818:
1798:
1795:
1792:
1789:
1786:
1783:
1763:
1760:
1757:
1754:
1751:
1731:
1726:
1722:
1718:
1715:
1712:
1709:
1689:
1669:
1647:
1643:
1620:
1616:
1612:
1609:
1606:
1603:
1600:
1595:
1591:
1570:
1567:
1564:
1561:
1541:
1521:
1518:
1515:
1492:
1489:
1484:
1480:
1459:
1456:
1453:
1450:
1447:
1444:
1424:
1421:
1418:
1415:
1412:
1409:
1389:
1386:
1383:
1354:
1351:
1348:
1344:
1340:
1337:
1334:
1331:
1328:
1303:
1283:
1280:
1277:
1274:
1242:
1239:
1236:
1233:
1230:
1210:
1207:
1204:
1201:
1172:
1169:
1166:
1163:
1143:
1111:
1108:
1105:
1102:
1082:
1056:
1036:
1033:
1028:
1025:
1022:
1018:
995:
975:
972:
969:
966:
946:
943:
940:
937:
934:
931:
911:
908:
905:
902:
882:
879:
876:
873:
845:
842:
837:
834:
831:
828:
825:
821:
817:
812:
809:
806:
803:
800:
796:
792:
787:
784:
781:
778:
775:
771:
767:
762:
759:
756:
753:
750:
746:
742:
737:
734:
731:
728:
725:
721:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
608:
588:
568:
565:
562:
559:
539:
536:
533:
530:
504:
501:
498:
494:
484:is bounded by
473:
470:
467:
464:
440:
437:
434:
431:
420:
419:
376:
365:
364:
353:
342:
339:
327:
324:
321:
318:
307:
295:
292:
289:
286:
269:the following
262:
259:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
190:
170:
150:
147:
133:
130:
127:
105:Martin Gardner
69:
68:
55:Find link tool
31:
29:
22:
15:
9:
6:
4:
3:
2:
3420:
3409:
3406:
3404:
3401:
3400:
3398:
3389:
3386:
3384:
3381:
3379:
3375:
3372:
3370:
3366:
3363:
3362:
3349:
3334:
3327:
3325:
3319:
3315:
3311:
3307:
3303:
3299:
3292:
3284:
3278:
3274:
3270:
3269:
3261:
3253:
3247:
3243:
3236:
3228:
3222:
3218:
3214:
3213:
3205:
3203:
3201:
3191:
3186:
3182:
3178:
3171:
3164:
3162:
3157:
3149:
3132:
3126:
3103:
3097:
3089:
3079:
3062:
3056:
3033:
3027:
3013:
3007:
3004:
3001:
2998:
2995:
2994:
2993:
2991:
2987:
2968:
2962:
2939:
2933:
2925:
2915:
2913:
2903:
2900:
2897:
2894:
2891:
2888:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2846:
2845:
2841:
2838:
2784:
2783:
2780:
2766:
2758:
2739:
2733:
2724:
2711:
2689:
2686:
2683:
2679:
2675:
2672:
2669:
2664:
2660:
2656:
2650:
2644:
2624:
2621:
2618:
2595:
2589:
2567:
2564:
2561:
2557:
2553:
2550:
2530:
2527:
2524:
2515:
2499:
2496:
2493:
2489:
2485:
2482:
2479:
2476:
2473:
2467:
2461:
2441:
2438:
2435:
2412:
2406:
2384:
2380:
2376:
2373:
2353:
2350:
2347:
2338:
2324:
2321:
2318:
2295:
2289:
2269:
2247:
2243:
2222:
2219:
2213:
2207:
2187:
2184:
2178:
2172:
2152:
2145:in iteration
2130:
2126:
2105:
2102:
2097:
2093:
2083:
2070:
2050:
2047:
2042:
2038:
2015:
2011:
2007:
2004:
2001:
1995:
1989:
1969:
1949:
1946:
1943:
1920:
1914:
1892:
1888:
1884:
1876:
1872:
1865:
1843:
1839:
1835:
1827:
1823:
1816:
1796:
1793:
1787:
1781:
1758:
1755:
1752:
1742:. During the
1724:
1720:
1713:
1710:
1707:
1687:
1667:
1645:
1641:
1618:
1614:
1610:
1607:
1604:
1601:
1598:
1593:
1589:
1565:
1559:
1539:
1519:
1516:
1513:
1504:
1490:
1487:
1482:
1478:
1457:
1454:
1448:
1442:
1422:
1419:
1413:
1407:
1387:
1384:
1381:
1373:
1368:
1352:
1349:
1346:
1342:
1338:
1332:
1326:
1319:
1315:
1301:
1278:
1272:
1264:
1259:
1257:
1256:
1237:
1234:
1231:
1205:
1199:
1186:
1167:
1161:
1141:
1132:
1125:
1106:
1100:
1080:
1071:
1067:
1054:
1034:
1031:
1026:
1023:
1020:
1016:
1006:
993:
970:
964:
944:
941:
935:
929:
906:
900:
877:
871:
862:
861:
857:
843:
840:
832:
829:
826:
819:
815:
807:
804:
801:
794:
790:
782:
779:
776:
769:
765:
757:
754:
751:
744:
740:
732:
729:
726:
719:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
606:
586:
563:
557:
534:
528:
519:
518:
502:
499:
496:
492:
468:
462:
452:
435:
429:
417:
416:
415:
412:
410:
406:
402:
398:
394:
390:
374:
351:
343:
340:
322:
316:
308:
290:
284:
276:
275:
274:
272:
268:
258:
241:
235:
232:
229:
226:
223:
220:
214:
208:
188:
168:
160:
156:
155:playing cards
131:
128:
125:
116:
112:
110:
106:
101:
98:
97:mathematician
95:
91:
87:
83:
79:
75:
65:
56:
51:
46:
42:
41:
37:
32:This article
30:
26:
21:
20:
3343:|quote=
3333:cite journal
3321:
3301:
3297:
3291:
3267:
3260:
3241:
3235:
3211:
3180:
3176:
3087:
3085:
3019:
3011:
2985:
2923:
2921:
2909:
2725:
2516:
2339:
2084:
1552:values that
1505:
1369:
1317:
1316:
1260:
1191:
1190:
1007:
863:
859:
858:
520:
454:
453:
421:
413:
408:
404:
400:
396:
392:
388:
366:
273:is applied:
266:
264:
152:
109:Donald Knuth
85:
81:
77:
73:
72:
62:January 2021
59:
33:
3273:74, 115–117
579:of the row
149:Formulation
100:John Conway
86:Bottomdrops
82:Bottomswops
3397:Categories
3152:References
2785:row length
1470:and since
53:; try the
40:link to it
2712:◻
2676:≤
2657:≤
2622:−
2565:−
2554:≤
2486:≤
2474:≤
2439:−
2377:≤
2311:, unless
2071:◻
2008:≤
2002:−
1947:−
1517:≥
1339:≤
1261:Proof by
1192:Theorem:
1055:◻
1032:−
994:◻
942:−
830:−
805:−
780:−
755:−
730:−
500:−
455:Theorem:
271:algorithm
43:. Please
3088:botdrops
3082:Botdrops
3016:Botswops
2986:topswops
2924:topdrops
2918:Topdrops
2517:Suppose
2340:Suppose
1907:. Hence
409:fannkuch
401:topswaps
397:topswops
389:topswops
267:topswops
261:Topswops
78:Topdrops
74:Topswops
3318:3619674
3008:2 1 3 4
3005:4 3 1 2
3002:2 1 4 3
2999:3 4 1 2
2996:2 1 3 4
2912:NP-hard
2543:. Then
2366:. Then
1435:. Thus
94:British
3316:
3279:
3248:
3223:
2582:since
2399:since
1532:. All
1374:. For
1318:Claim:
387:. The
88:) are
36:orphan
34:is an
3314:JSTOR
3217:76–82
3173:(PDF)
2755:is a
2165:Then
1183:in a
1122:in a
3374:OEIS
3365:OEIS
3348:help
3277:ISBN
3246:ISBN
3221:ISBN
2904:221
2901:191
2898:159
2528:>
2262:and
2118:and
1809:and
1611:<
1599:<
1154:and
1093:and
844:2833
407:and
265:For
159:suit
107:and
84:and
3306:doi
3185:doi
3181:411
2895:139
2892:113
2889:101
2842:19
2839:18
2836:17
2759:in
1253:th
599:to
550:to
181:to
3399::
3376::
3367::
3337::
3335:}}
3331:{{
3320:.
3312:.
3302:73
3300:.
3275:.
3219:.
3199:^
3179:.
3175:.
3160:^
2914:.
2886:80
2883:65
2880:51
2877:38
2874:30
2871:22
2868:16
2865:10
2833:16
2830:15
2827:14
2824:13
2821:12
2818:11
2815:10
2514:.
2337:.
2063:.
1367:.
1258:.
856:.
827:12
802:10
693:12
681:10
657:13
639:11
451:.
411:.
403:,
399:,
395:,
257:.
111:.
80:,
3350:)
3346:(
3326:.
3308::
3285:.
3254:.
3229:.
3193:.
3187::
3136:]
3133:1
3130:[
3127:A
3107:]
3104:1
3101:[
3098:A
3066:]
3063:1
3060:[
3057:A
3037:]
3034:1
3031:[
3028:A
2972:]
2969:1
2966:[
2963:A
2943:]
2940:1
2937:[
2934:A
2862:7
2859:4
2856:2
2853:1
2850:0
2812:9
2809:8
2806:7
2803:6
2800:5
2797:4
2794:3
2791:2
2788:1
2767:N
2743:)
2740:N
2737:(
2734:f
2690:1
2687:+
2684:k
2680:F
2673:r
2670:+
2665:k
2661:F
2654:)
2651:N
2648:(
2645:f
2625:2
2619:k
2599:]
2596:1
2593:[
2590:A
2568:1
2562:k
2558:F
2551:r
2531:1
2525:t
2500:1
2497:+
2494:k
2490:F
2483:1
2480:+
2477:r
2471:)
2468:N
2465:(
2462:f
2442:1
2436:k
2416:]
2413:1
2410:[
2407:A
2385:k
2381:F
2374:r
2354:1
2351:=
2348:t
2325:1
2322:=
2319:t
2299:]
2296:1
2293:[
2290:A
2270:t
2248:k
2244:d
2223:r
2220:=
2217:)
2214:N
2211:(
2208:f
2188:1
2185:=
2182:]
2179:1
2176:[
2173:A
2153:r
2131:k
2127:d
2106:1
2103:=
2098:1
2094:d
2051:1
2048:=
2043:1
2039:d
2016:k
2012:F
2005:r
1999:)
1996:N
1993:(
1990:f
1970:k
1950:1
1944:k
1924:]
1921:1
1918:[
1915:A
1893:k
1889:d
1885:=
1882:]
1877:k
1873:d
1869:[
1866:A
1844:k
1840:d
1836:=
1833:]
1828:k
1824:d
1820:[
1817:A
1797:t
1794:=
1791:]
1788:1
1785:[
1782:A
1762:)
1759:1
1756:+
1753:r
1750:(
1730:]
1725:k
1721:d
1717:[
1714:A
1711:=
1708:t
1688:r
1668:1
1646:k
1642:d
1619:k
1615:d
1608:.
1605:.
1602:.
1594:1
1590:d
1569:]
1566:1
1563:[
1560:A
1540:k
1520:2
1514:k
1491:1
1488:=
1483:2
1479:F
1458:1
1455:=
1452:]
1449:1
1446:[
1443:A
1423:0
1420:=
1417:)
1414:N
1411:(
1408:f
1388:1
1385:=
1382:k
1353:1
1350:+
1347:k
1343:F
1336:)
1333:N
1330:(
1327:f
1302:k
1282:]
1279:1
1276:[
1273:A
1241:)
1238:1
1235:+
1232:N
1229:(
1209:)
1206:N
1203:(
1200:f
1171:)
1168:N
1165:(
1162:f
1142:N
1110:)
1107:N
1104:(
1101:f
1081:N
1035:1
1027:1
1024:+
1021:N
1017:2
974:]
971:1
968:[
965:A
945:1
939:]
936:1
933:[
930:A
910:]
907:1
904:[
901:A
881:]
878:1
875:[
872:A
841:=
836:)
833:1
824:(
820:2
816:+
811:)
808:1
799:(
795:2
791:+
786:)
783:1
777:9
774:(
770:2
766:+
761:)
758:1
752:5
749:(
745:2
741:+
736:)
733:1
727:2
724:(
720:2
699:4
696:,
690:,
687:3
684:,
678:,
675:9
672:,
669:1
666:,
663:6
660:,
654:,
651:5
648:,
645:8
642:,
636:,
633:2
630:,
627:7
607:N
587:1
567:]
564:N
561:[
558:A
538:]
535:1
532:[
529:A
517:.
503:1
497:N
493:2
472:)
469:N
466:(
463:f
439:)
436:N
433:(
430:f
375:1
352:1
326:]
323:1
320:[
317:A
306:)
294:]
291:1
288:[
285:A
245:]
242:N
239:[
236:A
233:,
230:.
227:.
224:.
221:,
218:]
215:1
212:[
209:A
189:N
169:1
132:5
129:=
126:N
64:)
60:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.