%I #38 Jan 15 2026 07:46:28

%S 1,4,6,8,10,12,14,15,17,18,19,21,22,23,24,26,28,29,30,32,33,35,36,38,

%T 39,41,42

%N Flipping burnt pancakes. Given a sorted stack of n burnt pancakes of different sizes (smallest on top, ..., largest at the bottom), each with its burnt side up, a(n) is the number of spatula flips needed to restore them to their initial order but with the burnt sides down.

%C In a 'spatula flip', a spatula is inserted below any pancake and all pancakes above the spatula are lifted and replaced in reverse order.

%C 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.

%D 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).

%D M.H. Heydari, I.H. Sudborough, "On the Diameter of the Pancake Network", Journal of Algorithms, 25:1, (1997), 67-34.

%H Josef Cibulka, <a href="https://doi.org/10.1016/j.tcs.2010.11.028">On average and highest number of flips in pancake sorting</a>, Theoretical Computer Science, 412:8-10, (2011) 822-834.

%H David S. Cohen and Manuel Blum, <a href="https://doi.org/10.1016/0166-218X(94)00009-3">On the problem of sorting burnt pancakes</a>, Discrete Applied Mathematics, 61:2 (1995) 105-120.

%H Jacob Goodman, Bill Gates & Christos Papadimitriou, John Conway, <a href="https://web.archive.org/web/20030707181201/http://www.math.uiuc.edu/~west/openp/pancake.html">The Pancake Problems (1975, 1979, 1973)</a>.

%H Gerold Jäger and Nacim Oijid, <a href="https://arxiv.org/abs/2601.09447">Exact number of flips required to sort a burnt stack of pancakes</a>, arXiv:2601.09447 [math.CO], 2026.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Pancake_sorting">Pancake sorting</a>.

%F a(n) <= A078941(n). a(n+1) <= a(n) + 2 (by Cohen, Blum, 1995).

%F From _Gerold Jager_, Jan 05 2026: (Start)

%F floor ((3n+3)/2) <= a(n) <= floor ((3n+3)/2) + 2 (by Cibulka, 2011).

%F a(n) = floor ((3n+3)/2) for all n = 3 mod 4 (by Heydari, Sudborough, 1997, and Cibulka, 2011). (End)

%Y Cf. A078941, A058986, A067607, A092113.

%K nonn,more

%O 1,2

%A _Dean Hickerson_, Dec 18 2002

%E a(19)-a(27) from Bouzy, 2016, communicated by _Gerold Jager_, Jan 05 2026