OFFSET
1,2
COMMENTS
In a 'spatula flip', a spatula is inserted below any pancake and all pancakes above the spatula are lifted and replaced in reverse order.
The conjecture that this initial configuration is a worst case for the general problem of burnt pancakes has been disproved for n=15 by Cibulka, 2011.
REFERENCES
B. Bouzy, "Burnt Pancake Problem: New Lower Bounds on the Diameter and New Experimental Optimality Ratios", Proceedings of the Ninth Annual Symposium on Combinatorial Search, SOCS 2016, Tarrytown, NY, USA, AAAI Press (2016).
LINKS
Josef Cibulka, On average and highest number of flips in pancake sorting, Theoretical Computer Science, 412:8-10, (2011) 822-834.
David S. Cohen and Manuel Blum, On the problem of sorting burnt pancakes, Discrete Applied Mathematics, 61:2 (1995) 105-120.
Jacob Goodman, Bill Gates & Christos Papadimitriou, John Conway, The Pancake Problems (1975, 1979, 1973).
Mohammad H. Heydari and I. Hal Sudborough, On the Diameter of the Pancake Network, Journal of Algorithms, 25(1) (1997), 67-94.
Gerold Jäger and Nacim Oijid, Exact number of flips required to sort a burnt stack of pancakes, arXiv:2601.09447 [math.CO], 2026.
Richard E. Korf, Minimizing Disk I/O in Two-Bit Breadth-First Search, In Proceedings of the 23rd AAAI Conf. on Artificial Intelligence (AAAI'08). AAAI Press, (2008), 317-324.
Wikipedia, Pancake sorting.
FORMULA
a(n) <= A078941(n). a(n+1) <= a(n) + 2 (by Cohen, Blum, 1995).
From Gerold Jager, Jan 05 2026: (Start)
floor ((3n+3)/2) <= a(n) <= floor ((3n+3)/2) + 2 (by Cibulka, 2011).
a(n) = (3n+3)/2 if n == 3 mod 4 and n != 7, 11 (by Heydari, Sudborough, 1997, and Cibulka, 2011). (End)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Dean Hickerson, Dec 18 2002
EXTENSIONS
a(19)-a(27) from Bouzy, 2016, communicated by Gerold Jager, Jan 05 2026
STATUS
approved