%I A058986
%S A058986 0,1,3,4,5,7,8,9,10,11,13,14,15,16,17,18,19
%N A058986 Sorting by prefix reversal. 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] 
               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 17n / 16. For sufficiently large n, this is always larger 
               than the triangle.
%C A058986 Marc Lebrun writes that in 1975 he was involved with a group called "People's 
               Computer Company" and among the many early computer games they created 
               and popularized was one called "Reverse", which we published in our 
               newspaper. See link.
%D A058986 Shogo Asai, Yuusuke Kounoike, Yuji Shinano and Keiichi Kaneko, Computing 
               the Diameter of 17-Pancake Graph Using a PC Cluster, Proc. Euro-Par 
               2006, LNCS 4128, pp. 1114-1124, 2006 Springer Verlag
%D A058986 Bafna, Vineet and Pavel Pevzner. 1996. Genome rearrangements and sorting 
               by reversals. SIAM Journal on Computing 25:272-289.
%D A058986 Bergeron, Anne. 2005. A very elementary presentation of the Hannenhalli-Pevzner 
               theory. Discrete Applied Mathematics 146:134-145.
%D A058986 Bergeron, Anne and Francois Strasbourg. 2001. Experiments in computing 
               sequences of reversals. Proceedings of the First International Workshop 
               on Algorithms in Bioinformatics, pp. 164-174. Berlin: Springer-Verlag.
%D A058986 Caprara, Alberto. 1997. Sorting by reversals is difficult. Proceedings 
               of RECOMB '97: The First International Conference on Computational 
               Molecular Biology, pp. 75-83. New York: ACM Press.
%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 B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough 
               and W. Voit, An (18/11)n upper bound for sorting by prefix reversals, 
               to appear in Theoretical Computer Science, 2008.
%D A058986 Harry Dweighter ["Harried Waiter", pseudonym of Jacob E Goodman], Problem 
               E2569, Amer. Math. Monthly, 82 (1975), 1010. Comments by M. R. Garey, 
               D. S. Johnson and S. Lin, loc. cit. 84 (1977), 296.
%D A058986 W. H. Gates and C. H. Padadimitriou, Bounds for sorting by prefix reversal, 
               Discrete Math. 27 (1979), 47-57.
%D A058986 E. Gy\"{o}ri and G. Tur\'{a}n, Stack of pancakes, Studia Sci. Math. Hungar., 
               13 (1978), 133-137.
%D A058986 Hannenhalli, Sridhar and Pavel A. Pevzner. 1999. Transforming cabbage 
               into turnip: polynomial algorithm for sorting signed permutations 
               by reversals. Journal of the ACM 48:1-27.
%D A058986 Brian Hayes, Sorting out the genome, Amer. Scientist, 95 (2007), 386-391.
%D A058986 Kececioglu, J. D. and D. Sankoff. 1995. Exact and approximation algorithms 
               for sorting by reversal, with application to genome rearrangement. 
               Algorithmica 13:180-210.
%D A058986 Yuusuke Kounoike, Keiichi Kaneko and Yuji Shinano, Computing the Diameters 
               of 14- and 15-pancake Graphs, Proc. International Symposium on Parallel 
               Architectures, Algorithms and Networks(ISPAN 2005), pp. 490-495.
%D A058986 Tannier, Eric and Marie-France Sagot. 2004. Sorting by reversals in subquadratic 
               time. Proceedings of the 15th Annual Symposium on Combinatorial Pattern 
               Matching, pp. 1-13. Berlin: Springer-Verlag.
%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 Marc Lebrun et al., <a href="http://www.svipx.com/pcc/gameslist.html">
               See under V1N5</a>
%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> [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), 
               Oct 13 2008]
%H A058986 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/doc/sg.txt">
               My favorite integer sequences</a>, in Sequences and their Applications 
               (Proceedings of SETA '98).
%H A058986 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               PancakeSorting.html">Pancake Sorting</a>
%H A058986 <a href="Sindx_So.html#sorting">Index entries for sequences related to 
               sorting</a>
%F A058986 It is known that a(n) >= n+1 for n >= 6, a(n) >= 17n/16 if n is a multiple 
               of 16 (so a(32) >= 34) and a(n) <= (5n+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
%Y A058986 Cf. A067607, A078941 and A078942.
%Y A058986 Sequence in context: A039233 A075748 A039177 this_sequence A078358 A152012 
               A039131
%Y A058986 Adjacent sequences: A058983 A058984 A058985 this_sequence A058987 A058988 
               A058989
%K A058986 nonn,nice,hard
%O A058986 1,3
%A A058986 N. J. A. Sloane (njas(AT)research.att.com), 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.