Assume that n numbered pancakes are stacked, and that a spatula can be used to reverse the order of the top k pancakes for 2<=k<=n. Then the pancake sorting problem asks how many such "prefix reversals" are sufficient to sort an arbitrary stack. The maximum numbers of flips a_n needed to sort a random stack of n = 1, 2, 3, ... pancakes are 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, ... (OEIS A058986), with the number of maximal stacks for n = 2, 3, ... being 1, 1, 3, 20, 2, 35, 455, ... (OEIS A067607). The following table (OEIS A092113) gives the numbers of stacks of n pancakes requiring k flips. A flattened version is shown above as a binary plot.

pancake theorem | tower of Hanoi

pancake