This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A058986 #171 Feb 16 2025 08:32:43 %S A058986 0,1,3,4,5,7,8,9,10,11,13,14,15,16,17,18,19,20,22 %N A058986 Sorting by prefix reversal (or "flipping pancakes"). You can only reverse segments that include the initial term of the current permutation; a(n) is the number of reversals that are needed to transform an arbitrary permutation of n letters to the identity permutation. %C A058986 "The chef in our place is sloppy and when he prepares a stack of pancakes they come out all different sizes. Therefore when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top and so on, down to the largest at the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (as a function a(n) of n) that I will ever have to use to rearrange them?" [Dweighter] %C A058986 J. K. McLean (jkmclean(AT)webone.com.au): If the worst case for n pancakes is x flips, then the worst case for n+1 pancakes can be no greater than x+2 flips. Getting the n+1 pancake to the bottom of the pile will require 0, 1 or 2 flips, after which you can sort the n remaining pancakes in at most x flips. %C A058986 Comments based on email message from Brian Hayes, Oct 10 2007: (Start) %C A058986 We are interested in the diameter of the graph where the vertices are all possible permutations of n elements and an edge connects p(i) and p(j) if some allowed reversal transforms p(i) into p(j). %C A058986 There are at least two dimensions to consider in describing the various sorting-by-reversal problems: (a) Are the elements of the sequence signed or unsigned? and (b) Are we constrained to work only from one end of the sequence? %C A058986 The standard pancake problem has unsigned elements and allows moves only from the top of the stack; the diameter is given by the present sequence. %C A058986 The "burnt-pancake" problem has signed elements and allows moves only from the top of the stack. This is sequence A078941 (and also A078942). %C A058986 The biologically-inspired sorting problems I was writing about in the Amer. Scientist 2007 column dispense with the one-end-only constraint. You're allowed to reverse any segment of contiguous elements, anywhere in the permutation. For the unsigned case, a(n) = n-1 (cf. Kececioglu and Sankoff). %C A058986 Finally there is the signed case without the one-end constraint. This was the main subject of my column and corresponds to sequence A131209. (End) %C A058986 Brian Goodwin (brian_goodwin(AT)yahoo.com), Aug 22 2005, comments that the terms so far match the beginning of the following triangle: %C A058986 0 %C A058986 1 %C A058986 3 4 5 %C A058986 7 8 9 10 11 %C A058986 13 14 15 16 17 18 19 %C A058986 21 22 23 24 25 26 27 28 29 %C A058986 31 32 ... %C A058986 Is this a coincidence? Answer from Mikola Lysenko (mclysenk(AT)mtu.edu), Dec 09 2006: Unfortunately, Yes! That triangular sequence has the closed form: a(n) = n - 1 + floor(sqrt(n-2)). However, Gates and Papadimitrou establish a lower bound on the pancake sequence of at least (17/16)*n. For sufficiently large n, this is always larger than the number in the triangle. %C A058986 Marc Lebrun writes that in 1975 he was involved with a group called the "People's Computer Company" and among the many early computer games they created and popularized was one called "Reverse", which they published in their newspaper. See link. %C A058986 M. Peczarski and I affirm the value a(19) = 22 as given by Simon Singh. Firstly, a(19) >= 22 as stated in the paper by Heydari Sudborough. This statement is mentioned on page 93. There two permutations of order 19 are given which need at least 22 flips. These permutations are 1,7,5,3,6,4,2,8,14,12,10,13,11,9,15,17,19,16,18 and 1,7,5,3,6,4,2,8,14,12,10,13,11,9,15,18,16,19,17. Making use of a branch-and-bound algorithm, we can confirm that their statement is correct. Together with the result that a(18) = 20, this gives a(19) = 22. Both values a(18) = 20 and a(19) = 22 were also proved in the paper by Cibulka. - _Gerold Jäger_, Oct 29 2020 %D A058986 J. J. Chew, III (jjchew(AT)math.utoronto.ca), personal communication, Jan 15 and Feb 08 2001, computed a(10) - a(13). %D A058986 E. Györi and G. Turán, Stack of pancakes, Studia Sci. Math. Hungar., 13 (1978), 133-137. %H A058986 Kazuyuki Amano, <a href="https://doi.org/10.1587/transinf.2024FCL0002">(15/14)n Flips are (almost) Sufficient to Sort Heydari and Sudborough's Pancake Stack</a>, IEICE Trans. Info. Sys. (2024). See p. 1. %H A058986 Shogo Asai, Yuusuke Kounoike, Yuji Shinano and Keiichi Kaneko, <a href="https://doi.org/10.1007/11823285_117">Computing the Diameter of 17-Pancake Graph Using a PC Cluster</a>, Proc. Euro-Par 2006, LNCS 4128, pp. 1114-1124, 2006 Springer Verlag. %H A058986 Vineet Bafna and Pavel Pevzner, <a href="https://doi.org/10.1137/S0097539793250627">Genome rearrangements and sorting by reversals</a>, SIAM Journal on Computing 25:272-289 (1996). %H A058986 Anne Bergeron, <a href="https://doi.org/10.1016/j.dam.2004.04.010">A very elementary presentation of the Hannenhalli-Pevzner theory</a>, Discrete Applied Mathematics 146:134-145 (2005). %H A058986 Anne Bergeron, and Francois Strasbourg, <a href="https://www.researchgate.net/publication/221313399_Experiments_in_Computing_Sequences_of_Reversals">Experiments in computing sequences of reversals</a>, Proceedings of the First International Workshop on Algorithms in Bioinformatics, 2001, pp. 164-174. Berlin: Springer-Verlag. %H A058986 Laurent Bulteau, Guillaume Fertin, Irena Rusu, <a href="https://arxiv.org/abs/1111.0434">Pancake Flipping is Hard</a>, arXiv:1111.0434 [cs.CC], Nov 10, 2011. %H A058986 Alberto Caprara, <a href="https://www.cs.oberlin.edu/~asharp/cs365/papers/C97.pdf">Sorting by reversals is difficult</a>, Proceedings of RECOMB '97: The First International Conference on Computational Molecular Biology, 1997, pp. 75-83. New York: ACM Press. %H A058986 B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough and W. Voit, <a href="https://doi.org/10.1016/j.tcs.2008.04.045">An (18/11)n upper bound for sorting by prefix reversals</a>, Theoret. Comput. Sci. 410 (2009), no. 36, 3372-3390. %H A058986 J. Cibulka, <a href="https://doi.org/10.1016/j.tcs.2010.11.028">On average and highest number of flips in pancake sorting</a>, Theoret. Comput. Sci. 412 (2011), 822-834 %H A058986 C. Dalfó and Miquel A. Fiol, <a href="https://doi.org/10.1016/j.laa.2020.03.015">Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups</a>, Linear Algebra Appl. 597 (2020), 94-112; <a href="https://doi.org/10.48550/arXiv.1906.05851">arXiv:1906.05851 [math.CO]</a>. %H A058986 F. Javier de Vega, <a href="https://arxiv.org/abs/2003.13378">An extension of Furstenberg's theorem of the infinitude of primes</a>, arXiv:2003.13378 [math.NT], 2020. %H A058986 Harry Dweighter ["Harried Waiter", pseudonym of Jacob E Goodman], <a href="http://www.jstor.org/stable/2318260">Problem E2569</a>, Amer. Math. Monthly, 82 (1975), 1010. <a href="https://www.jstor.org/stable/2318878">Comments</a> by M. R. Garey, D. S. Johnson and S. Lin, loc. cit. 84 (1977), 296. %H A058986 W. H. Gates and C. H. Padadimitriou, <a href="https://doi.org/10.1016/0012-365X(79)90068-2">Bounds for sorting by prefix reversal</a>, Discrete Math. 27 (1979), 47-57. %H A058986 Sridhar Hannenhalli and Pavel A. Pevzner, <a href="https://www.researchgate.net/publication/2667364_Transforming_Cabbage_into_Turnip_Polynomial_Algorithm_for_Sorting_Signed_Permutations_by_Reversals">Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals</a>, Journal of the ACM 48:1-27 (1999). %H A058986 Brian Hayes, <a href="https://www.jstor.org/stable/27859020">Computing Science: Sorting out the genome</a>, Amer. Scientist, 95 (2007), 386-391. %H A058986 M. H. Heydari and I. Hal Sudborough, <a href="http://dx.doi.org/10.1006/jagm.1997.0874">On the diameter of the pancake network</a>,J. Algorithms 25 (1997) no 1, 67-94. %H A058986 J. D. Kececioglu, and D. Sankoff, <a href="https://www.researchgate.net/publication/226954865_Exact_and_Approximation_Algorithms_for_Sorting_by_Reversals_with_Application_to_Genome_Rearrangement">Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement</a>, Algorithmica (1995) 13:180. %H A058986 Yuichi Komano and Takaaki Mizuki, <a href="https://doi.org/10.1007/978-3-031-32636-3_13">Card-Based Zero-Knowledge Proof Protocol for Pancake Sorting</a>, Int'l Conf. Info. Tech. Comm. Sec., Innov. Security Sol. Info. Tech. Comm. (SecITC 2022), Lecture Notes Comp. Sci. (LNCS Vol. 13809), Springer, Cham, pp. 222-239. %H A058986 Yuusuke Kounoike, Keiichi Kaneko and Yuji Shinano, <a href="https://doi.org/10.1109/ISPAN.2005.31">Computing the Diameters of 14- and 15-pancake Graphs</a>, Proc. International Symposium on Parallel Architectures, Algorithms and Networks(ISPAN 2005), pp. 490-495. %H A058986 Marc Lebrun et al., <a href="http://www.svipx.com/pcc/gameslist.html">The PCC Games List</a>, Section V1N5. %H A058986 Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/pancakes.htm">Pancakes</a> %H A058986 Ivars Peterson, <a href="http://www.sciencenews.org/articles/20060902/mathtrek.asp">Pancake Sorting</a>. %H A058986 Ivars Peterson, <a href="http://www.maa.org/mathtourist/mathtourist_10_9_08.html">Improved Pancake Sorting</a> %H A058986 J. Sawada and A. Williams, <a href="http://www.cis.uoguelph.ca/~sawada/papers/pancake_successor.pdf">Successor rules for flipping pancakes and burnt pancakes</a>, Preprint 2015; Theoretical Computer Science, Volume 609, Part 1, Jan 04 2016, Pages 60-75. %H A058986 Simon Singh, <a href="http://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman">Flipping pancakes with mathematics</a>, Blog Posting, Nov 14 2013. [States that a(18)=20, a(19)=22] %H A058986 N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98). %H A058986 Katie Steckles and Brady Haran, <a href="https://youtu.be/m3drS_8BpU0">Pancake Numbers</a>, Numberphile video (2017). %H A058986 Eric Tannier, and Marie-France Sagot, <a href="https://doi.org/10.1007/978-3-540-27801-6_1">Sorting by reversals in subquadratic time</a>, Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, 2004, pp. 1-13. Berlin: Springer-Verlag. %H A058986 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PancakeSorting.html">Pancake Sorting</a> %H A058986 Douglas B. West, <a href="http://www.math.uiuc.edu/~west/openp/pancake.html">The Pancake Problems (1975, 1979, 1973)</a> %H A058986 <a href="/index/So#sorting">Index entries for sequences related to sorting</a> %F A058986 It is known that a(n) >= n+1 for n >= 6, a(n) >= (17/16)*n if n is a multiple of 16 (so a(32) >= 34) and a(n) <= (5*n+5)/3. %F A058986 There is an improved asymptotic upper bound of (18/11)*n + O(1) for the number of prefix reversals to sort permutations of length n given in the Chitturi et al. paper. - Ivan Hal Sudborough (hal_sud(AT)yahoo.com), Jul 02 2008 %e A058986 For n = 3, the stack of pancakes with radii (1, 3, 2) requires a(3) = 3 flips to sort: Starting with (1, 3, 2), flip the top two pancakes to get (3, 1, 2), then flip the entire stack to get (2, 1, 3), then flip the top two pancakes again to get (1, 2, 3). %Y A058986 Cf. A067607, A078941, A078942, A092113. %Y A058986 First differences: A359141. %K A058986 nonn,nice,hard,more %O A058986 1,3 %A A058986 _N. J. A. Sloane_, Jan 17 2001, Oct 12 2007 %E A058986 Typo in value for a(5) corrected by _Ed Pegg Jr_, Jan 02 2002 %E A058986 a(14)-a(17) from Ivan Hal Sudborough (hal_sud(AT)yahoo.com), Jul 02 2008. The new upper bounds for n = 14, 15, 16 and 17 are found in the articles by Asai et al. and Kounoike et al. %E A058986 Simon Singh's blog gives values for a(18) and a(19). It is not clear if these have been proved to be correct. - _N. J. A. Sloane_, Dec 11 2013