Pancake numbers

From Rosetta Code
Task
Pancake numbers
You are encouraged to solve this task according to the task description, using any language you may know.

Adrian Monk has problems and an assistant, Sharona Fleming. Sharona can deal with most of Adrian's problems except his lack of punctuality paying her remuneration. 2 pay checks down and she prepares him pancakes for breakfast. Knowing that he will be unable to eat them unless they are stacked in ascending order of size she leaves him only a skillet which he can insert at any point in the pile and flip all the above pancakes, repeating until the pile is sorted. Sharona has left the pile of n pancakes such that the maximum number of flips is required. Adrian is determined to do this in as few flips as possible. This sequence n->p(n) is known as the Pancake numbers.

The task is to determine p(n) for n = 1 to 9, and for each show an example requiring p(n) flips.

Sorting_algorithms/Pancake_sort actually performs the sort some giving the number of flips used. How do these compare with p(n)?

Few people know p(20), generously I shall award an extra credit for anyone doing more than p(16).


References
  1. Bill Gates and the pancake problem
  2. A058986



AWK

This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
# syntax: GAWK -f PANCAKE_NUMBERS.AWK
# converted from C
BEGIN {
    for (i=0; i<4; i++) {
      for (j=1; j<6; j++) {
        n = i * 5 + j
        printf("p(%2d) = %2d  ",n,main(n))
      }
      printf("\n")
    }
    exit(0)
}
function main(n,  adj,gap,sum) {
    gap = 2
    sum = 2
    adj = -1
    while (sum < n) {
      adj++
      gap = gap * 2 - 1
      sum += gap
    }
    return(n + adj)
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23

BASIC

Applesoft BASIC

Works with: Chipmunk Basic
Works with: QBasic
100 HOME
110 FOR I = 0 TO 3
120  FOR J = 1 TO 5
130   LET N = (I * 5) + J
140   LET C = C + 1
150   GOSUB 200
160   PRINT "p("; N; ") = "; P; "  "
170  NEXT J
180 NEXT I
190 END
200 REM pancake(n)
210  LET G = 2 : LET S = 2 : LET A = -1
220  IF S < N THEN LET A = A + 1 : LET G = (G * 2) - 1 : LET S = S + G
230  IF S >= N THEN LET P = N + A : RETURN
240 GOTO 220

BASIC256

Translation of: FreeBASIC
c = 0

for i = 0 to 3
	for j = 1 to 5
		n = (i * 5) + j
		c += 1
		print "p("; rjust(string(n),2); ") = "; pancake(n); "  ";
		if c mod 5 = 0 then print
	next j
next i
end

function pancake(n)
	gap = 2
	sum = 2
	adj = -1
	while sum < n
		adj += 1
		gap = (gap * 2) - 1
		sum += gap
	end while
	return rjust(string(n + adj), 2)
end function
Output:
Same as FreeBASIC entry.

Chipmunk Basic

Works with: Chipmunk Basic version 3.6.4
Translation of: FreeBASIC
100 c = 0
110 for i = 0 to 3
120   for j = 1 to 5
130     n = (i*5)+j
140     c = c+1
150     print "p(";format$(n,"##");") = ";format$(pancake(n),"##");"  ";
160     if c mod 5 = 0 then print
170   next j
180 next i
190 end
200 function pancake(n)
210   gap = 2
220   sum = 2
230   adj = -1
240   while sum < n
250     adj = adj+1
260     gap = (gap*2)-1
270     sum = sum+gap
280   wend
290   pancake = n+adj
300 end function
Output:
Same as FreeBASIC entry.

Gambas

Translation of: FreeBASIC
Public Sub Main() 
  
  Dim i As Integer, j As Integer, c As Integer = 0, n As Integer

  For i = 0 To 3 
    For j = 1 To 5 
      n = (i * 5) + j 
      c += 1 
      Print "p("; Format$(n, "##"); ") = "; Format$(pancake(n), "##"); "  ";
      If c Mod 5 = 0 Then Print 
    Next 
  Next
  
End 

Function pancake(n As Integer) As Integer 
  
  Dim gap As Integer = 2, sum As Integer = 2, adj As Integer = -1 

  While sum < n 
    adj += 1 
    gap = (gap * 2) - 1 
    sum += gap 
  Wend 
  Return n + adj 
  
End Function
Output:
Same as FreeBASIC entry.

GW-BASIC

Works with: Chipmunk Basic
Works with: MSX-BASIC
Works with: PC-BASIC version any
Works with: QBasic
100 CLS
110 FOR I = 0 TO 3
120  FOR J = 1 TO 5
130   N = (I*5)+J
140   C = C+1
150   GOSUB 200
160   PRINT USING "p(##) = ##  ";N;PANCAKE
170  NEXT J
180 NEXT I
190 END
200 REM pancake(n)
210  GAP = 2
220  SUM = 2
230  ADJ = -1
240  IF SUM < N THEN ADJ = ADJ+1 : GAP = (GAP*2)-1 : SUM = SUM+GAP
250  IF SUM >= N THEN PANCAKE = N+ADJ : RETURN
260 GOTO 240
Output:
p(1) = 0
p(2) = 1
p(3) = 3
p(4) = 4
p(5) = 5
p(6) = 7
p(7) = 8
p(8) = 9
p(9) = 10
p(10) = 11
p(11) = 13
p(12) = 14
p(13) = 15
p(14) = 16
p(15) = 17
p(16) = 18
p(17) = 19
p(18) = 20
p(19) = 21
p(20) = 23

MSX Basic

The GW-BASIC solution works without any changes.

PureBasic

Translation of: FreeBASIC
Procedure pancake(n)
  gap.i = 2
  sum.i = 2
  adj.i = -1
  While sum < n
    adj + 1
    gap = (gap * 2) - 1
    sum + gap
  Wend
  ProcedureReturn n + adj
EndProcedure

OpenConsole()
Define.i i, j, c, n

For i = 0 To 3
  For j = 1 To 5
    n = (i * 5) + j
    c + 1
    Print("p(" + RSet(Str(n),2) + ") = " + RSet(Str(pancake(n)),2) + "  ") 
    If Mod(c, 5 )= 0: PrintN(""): EndIf
  Next j
Next i

Input()
CloseConsole()
Output:
Same as FreeBASIC entry.

QBasic

Works with: QBasic version 1.1
Works with: QuickBasic version 4.5
Translation of: FreeBASIC
DECLARE FUNCTION pancake! (n)

FOR i = 0 TO 3
    FOR j = 1 TO 5
        n = (i * 5) + j
        c = c + 1
        PRINT USING "p(##) = ##  "; n; pancake(n);
        IF c MOD 5 = 0 THEN PRINT
    NEXT j
NEXT i

FUNCTION pancake (n)
    gap = 2
    sum = 2
    adj = -1
    WHILE sum < n
        adj = adj + 1
        gap = (gap * 2) - 1
        sum = sum + gap
    WEND
    pancake = n + adj
END FUNCTION
Output:
Same as FreeBASIC entry.

True BASIC

Translation of: QBasic
FUNCTION pancake(n)
    LET gap = 2
    LET sum = 2
    LET adj = -1
    DO while sum < n
       LET adj = adj+1
       LET gap = (gap*2)-1
       LET sum = sum+gap
    LOOP
    LET pancake = n+adj
END FUNCTION

FOR i = 0 to 3
    FOR j = 1 to 5
        LET n = (i*5)+j
        LET c = c+1
        PRINT  using "p(##) = ##  ": n, pancake(n);
        IF remainder(round(c),5) = 0 then PRINT
    NEXT j
NEXT i
END
Output:
Same as QBasic entry.

Yabasic

Translation of: FreeBASIC
for i = 0 to 3
    for j = 1 to 5
        n = (i * 5) + j
        c = c + 1
        print "p(", n using "##", ") = "; 
		print pancake(n) using "##", "  ";
        if mod(c, 5) = 0  print
    next j
next i
end

sub pancake(n)
    gap = 2
    sum = 2
    adj = -1
    while sum < n
        adj = adj + 1
        gap = (gap * 2) - 1
        sum = sum + gap
    wend
    return n + adj
end sub
Output:
Same as FreeBASIC entry.

C

This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: Go
#include <stdio.h>

int pancake(int n) {
    int gap = 2, sum = 2, adj = -1;
    while (sum < n) {
        adj++;
        gap = gap * 2 - 1;
        sum += gap;
    }
    return n + adj;
}

int main() {
    int i, j;
    for (i = 0; i < 4; i++) {
        for (j = 1; j < 6; j++) {
            int n = i * 5 + j;
            printf("p(%2d) = %2d  ", n, pancake(n));
        }
        printf("\n");
    }
    return 0;
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23

C#

Translation of: C
using System;

public class Pancake
{
    private static int pancake(int n)
    {
        int gap = 2;
        int sum = 2;
        int adj = -1;
        while (sum < n)
        {
            adj++;
            gap = 2 * gap - 1;
            sum += gap;
        }
        return n + adj;
    }

    public static void Main(string[] args)
    {
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j < 6; j++)
            {
                int n = 5 * i + j;
                Console.Write($"p({n,2}) = {pancake(n),2}  ");
            }
            Console.WriteLine();
        }
    }
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5  
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11  
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17  
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  


C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <numeric>
#include <iomanip>

std::vector<int32_t> flip_stack(std::vector<int32_t>& stack, const int32_t index) {
	reverse(stack.begin(), stack.begin() + index);
	return stack;
}

std::pair<std::vector<int32_t>, int32_t> pancake(const int32_t number) {
	std::vector<int32_t> initial_stack(number);
	std::iota(initial_stack.begin(), initial_stack.end(), 1);
	std::map<std::vector<int32_t>, int32_t> stack_flips = { std::make_pair(initial_stack, 1) };
	std::queue<std::vector<int32_t>> queue;
	queue.push(initial_stack);

	while ( ! queue.empty() ) {
		std::vector<int32_t> stack = queue.front();
		queue.pop();

		const int32_t flips = stack_flips[stack] + 1;
		for ( int i = 2; i <= number; ++i ) {
			std::vector<int32_t> flipped = flip_stack(stack, i);
			if ( stack_flips.find(flipped) == stack_flips.end() ) {
				stack_flips[flipped] = flips;
				queue.push(flipped);
			}
		}
    }

	auto ptr = std::max_element(
		stack_flips.begin(), stack_flips.end(),
		[] ( const auto & pair1, const auto & pair2 ) {
	    	return pair1.second < pair2.second;
		}
	);

	return std::make_pair(ptr->first, ptr->second);
}

int main() {
	for ( int32_t n = 1; n <= 9; ++n ) {
		std::pair<std::vector<int32_t>, int32_t> result = pancake(n);
		std::cout << "pancake(" << n << ") = " << std::setw(2) << result.second << ". Example [";
		for ( uint64_t i = 0; i < result.first.size() - 1; ++i ) {
			std::cout << result.first[i] << ", ";
		}
		std::cout << result.first.back() << "]" << std::endl;
	}
}
Output:
pancake(1) =  1. Example [1]
pancake(2) =  2. Example [2, 1]
pancake(3) =  4. Example [1, 3, 2]
pancake(4) =  5. Example [2, 4, 1, 3]
pancake(5) =  6. Example [1, 3, 2, 5, 4]
pancake(6) =  8. Example [4, 6, 2, 5, 1, 3]
pancake(7) =  9. Example [1, 3, 7, 5, 2, 6, 4]
pancake(8) = 10. Example [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 11. Example [1, 2, 5, 8, 3, 6, 9, 4, 7]

Cowgol

This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
include "cowgol.coh";

sub pancake(n: uint8): (r: uint8) is
    var gap: uint8 := 2;
    var sum: uint8 := 2;
    var adj: int8 := -1;
    
    while sum < n loop
        adj := adj + 1;
        gap := gap * 2 - 1;
        sum := sum + gap;
    end loop;
    
    r := n + adj as uint8;
end sub;

# print 2-digit number
sub print2(n: uint8) is
    if n<10 then
        print_char(' ');
    else
        print_char(n/10 + '0');
    end if;
    print_char(n%10 + '0');
end sub;

# print item
sub print_item(n: uint8) is
    print("p(");
    print2(n);
    print(") = ");
    print2(pancake(n));
    print("  ");
end sub;

var i: uint8 := 0;
while i < 4 loop
    var j: uint8 := 1;
    while j < 6 loop
        print_item(i*5 + j);
        j := j + 1;
    end loop;
    print_nl();
    i := i + 1;
end loop;
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23

D

Translation of: C
import std.stdio;
import std.algorithm;
import std.random;
import std.range;

int pancake(int n) {
    int gap = 2, sum = 2, adj = -1;
	
    while (sum < n) {
        adj++;
        gap = 2 * gap - 1;
        sum += gap;
    }
	
    return n + adj;
}

Range pancakeSort(Range)(Range r) {
	foreach_reverse (immutable i; 2 .. r.length + 1) {
		immutable maxIndex = i - r[0 .. i].minPos!q{a > b}.length;
		
		if (maxIndex + 1 != i) {
			if (maxIndex != 0) {
				r[0 .. maxIndex + 1].reverse();
			}
			
			r[0 .. i].reverse();
		}
	}
	
	return r;
}

void main() {
	writeln("\nThe maximum number of flips to sort a given number of elements is:\n");
	
	foreach (i; 1..11)
	{
		auto data = iota(1, i+1).array;
		
		if (i != 1) {
			// Protection against the edge case data.lenght == 1 not handled by randomShuffle
			// where also data is invariant with regard to pancakeSort
			do 
				data.randomShuffle;
			while (data.isSorted);
		}
		
		auto sortedData = data.dup;
		sortedData.pancakeSort;
		
		writefln("pancake(%2d) = %2d  e.g  %s  ->  %s", i, pancake(i), data, sortedData);
	}
}
Output:
The maximum number of flips to sort a given number of elements is:

pancake( 1) =  0  e.g  [1]  ->  [1]
pancake( 2) =  1  e.g  [2, 1]  ->  [1, 2]
pancake( 3) =  3  e.g  [3, 2, 1]  ->  [1, 2, 3]
pancake( 4) =  4  e.g  [3, 1, 4, 2]  ->  [1, 2, 3, 4]
pancake( 5) =  5  e.g  [2, 4, 3, 5, 1]  ->  [1, 2, 3, 4, 5]
pancake( 6) =  7  e.g  [2, 5, 6, 1, 4, 3]  ->  [1, 2, 3, 4, 5, 6]
pancake( 7) =  8  e.g  [7, 1, 4, 6, 3, 5, 2]  ->  [1, 2, 3, 4, 5, 6, 7]
pancake( 8) =  9  e.g  [3, 1, 4, 5, 2, 8, 7, 6]  ->  [1, 2, 3, 4, 5, 6, 7, 8]
pancake( 9) = 10  e.g  [3, 6, 4, 9, 7, 1, 8, 2, 5]  ->  [1, 2, 3, 4, 5, 6, 7, 8, 9]

F#

// Pancake numbers. Nigel Galloway: October 28th., 2020
let pKake z=let n=[for n in 1..z-1->Array.ofList([n.. -1..0]@[n+1..z-1])]
            let e=let rec fG n g=match g with 0->n |_->fG (n*g) (g-1) in fG 1 z
            let rec fN i g l=match (Set.count g)-e with 0->(i,List.last l)
                                                       |_->let l=l|>List.collect(fun g->[for n in n->List.permute(fun g->n.[g]) g])|>Set.ofList
                                                           fN (i+1) (Set.union g l) (Set.difference l g|>Set.toList)
            fN 0 (set[[1..z]]) [[1..z]]

[1..9]|>List.iter(fun n->let i,g=pKake n in printfn "Maximum number of flips to sort %d elements is %d. e.g %A->%A" n i g [1..n])
Output:
Maximum number of flips to sort 1 elements is 0. e.g [1]->[1]
Maximum number of flips to sort 2 elements is 1. e.g [2; 1]->[1; 2]
Maximum number of flips to sort 3 elements is 3. e.g [1; 3; 2]->[1; 2; 3]
Maximum number of flips to sort 4 elements is 4. e.g [4; 2; 3; 1]->[1; 2; 3; 4]
Maximum number of flips to sort 5 elements is 5. e.g [5; 3; 1; 4; 2]->[1; 2; 3; 4; 5]
Maximum number of flips to sort 6 elements is 7. e.g [5; 3; 6; 1; 4; 2]->[1; 2; 3; 4; 5; 6]
Maximum number of flips to sort 7 elements is 8. e.g [7; 3; 1; 5; 2; 6; 4]->[1; 2; 3; 4; 5; 6; 7]
Maximum number of flips to sort 8 elements is 9. e.g [8; 6; 2; 4; 7; 3; 5; 1]->[1; 2; 3; 4; 5; 6; 7; 8]
Maximum number of flips to sort 9 elements is 10. e.g [9; 7; 5; 2; 8; 1; 4; 6; 3]->[1; 2; 3; 4; 5; 6; 7; 8; 9]


FreeBASIC

Maximum number of flips only

Translation of: Go
Dim As Integer num_pancakes = 20
Dim As Integer i, j, c = 0, n

Function pancake(n As Integer) As Integer
    Dim As Integer gap = 2, sum = 2, adj = -1
    While sum < n
        adj += 1
        gap = (gap * 2) - 1
        sum += gap
    Wend
    Return n + adj
End Function

For i = 0 To 3
    For j = 1 To 5
        n = (i * 5) + j
        c += 1
        Print Using "p(##) = ##  "; n; pancake(n); 
        If c Mod 5 = 0 Then Print
    Next j
Next i

Sleep
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23

Go

Maximum number of flips only

Translation of: Phix
package main

import "fmt"

func pancake(n int) int {
    gap, sum, adj := 2, 2, -1
    for sum < n {
        adj++
        gap = gap*2 - 1
        sum += gap
    }
    return n + adj
}

func main() {
    for i := 0; i < 4; i++ {
        for j := 1; j < 6; j++ {
            n := i*5 + j
            fmt.Printf("p(%2d) = %2d  ", n, pancake(n))
        }
        fmt.Println()
    }
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5  
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11  
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17  
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  

Maximum number of flips plus examples using exhaustive search

Translation of: Wren

And hence indirectly of Julia. Go has the same problem as Wren in not supporting slices as map keys and therefore having to convert them to/from strings.

Map order iteration is also undefined in Go even between individual runnings.

Not particularly fast - Julia is about 3 seconds faster on the same machine.

package main

import (
    "fmt"
    "strconv"
    "strings"
    "time"
)

type assoc map[string]int

// Converts a string of the form "[1 2]" into a slice of ints: {1, 2}
func asSlice(s string) []int {
    split := strings.Split(s[1:len(s)-1], " ")
    le := len(split)
    res := make([]int, le)
    for i := 0; i < le; i++ {
        res[i], _ = strconv.Atoi(split[i])
    }
    return res
}

// Merges two assocs into one. If the same key is present in both assocs
// its value will be the one in the second assoc.
func merge(m1, m2 assoc) assoc {
    m3 := make(assoc)
    for k, v := range m1 {
        m3[k] = v
    }
    for k, v := range m2 {
        m3[k] = v
    }
    return m3
}

// Finds the maximum value in 'dict' and returns the first key
// it finds (iteration order is undefined) with that value.
func findMax(dict assoc) string {
    max := -1
    maxKey := ""
    for k, v := range dict {
        if v > max {
            max = v
            maxKey = k
        }
    }
    return maxKey
}

// Creates a new slice of ints by reversing an existing one.
func reverse(s []int) []int {
    le := len(s)
    rev := make([]int, le)
    for i := 0; i < le; i++ {
        rev[i] = s[le-1-i]
    }
    return rev
}

func pancake(n int) (string, int) {
    numStacks := 1
    gs := make([]int, n)
    for i := 0; i < n; i++ {
        gs[i] = i + 1
    }
    goalStack := fmt.Sprintf("%v", gs)
    stacks := assoc{goalStack: 0}
    newStacks := assoc{goalStack: 0}
    for i := 1; i <= 1000; i++ {
        nextStacks := assoc{}
        for key := range newStacks {
            arr := asSlice(key)
            for pos := 2; pos <= n; pos++ {
                t := append(reverse(arr[0:pos]), arr[pos:len(arr)]...)
                newStack := fmt.Sprintf("%v", t)
                if _, ok := stacks[newStack]; !ok {
                    nextStacks[newStack] = i
                }
            }
        }
        newStacks = nextStacks
        stacks = merge(stacks, newStacks)
        perms := len(stacks)
        if perms == numStacks {
            return findMax(stacks), i - 1
        }
        numStacks = perms
    }
    return "", 0
}

func main() {
    start := time.Now()
    fmt.Println("The maximum number of flips to sort a given number of elements is:")
    for i := 1; i <= 10; i++ {
        example, steps := pancake(i)
        fmt.Printf("pancake(%2d) = %-2d  example: %s\n", i, steps, example)
    }
    fmt.Printf("\nTook %s\n", time.Since(start))
}
Output:
The maximum number of flips to sort a given number of elements is:
pancake( 1) = 0   example: [1]
pancake( 2) = 1   example: [2 1]
pancake( 3) = 3   example: [1 3 2]
pancake( 4) = 4   example: [3 1 4 2]
pancake( 5) = 5   example: [4 2 5 1 3]
pancake( 6) = 7   example: [5 3 6 1 4 2]
pancake( 7) = 8   example: [1 5 7 3 6 4 2]
pancake( 8) = 9   example: [3 7 1 5 8 2 6 4]
pancake( 9) = 10  example: [7 2 9 5 1 8 3 6 4]
pancake(10) = 11  example: [7 5 9 4 10 1 8 2 6 3]

Took 57.512153273s

Java

Fast approximation

Translation of: Go – Original algorithm from Phix
public class Pancake {
    private static int pancake(int n) {
        int gap = 2;
        int sum = 2;
        int adj = -1;
        while (sum < n) {
            adj++;
            gap = 2 * gap - 1;
            sum += gap;
        }
        return n + adj;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j < 6; j++) {
                int n = 5 * i + j;
                System.out.printf("p(%2d) = %2d  ", n, pancake(n));
            }
            System.out.println();
        }
    }
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5  
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11  
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17  
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  

With exhaustive search

Translation of: Kotlin

Uses a standard breadth-first search using a queue. Note that because java is very verbose at defining classes, we instead had pancake return a Map.Entry<List<Integer>, Integer> directly, rather than a dedicated named class. This is arguably bad practice, but keeps the snippet terse.

import static java.util.Comparator.comparing;
import static java.util.stream.Collectors.toList;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.stream.IntStream;


public class Pancake {

    private static List<Integer> flipStack(List<Integer> stack, int spatula) {
        List<Integer> copy = new ArrayList<>(stack);
        Collections.reverse(copy.subList(0, spatula));
        return copy;
    }

    private static Map.Entry<List<Integer>, Integer> pancake(int n) {
        List<Integer> initialStack = IntStream.rangeClosed(1, n).boxed().collect(toList());
        Map<List<Integer>, Integer> stackFlips = new HashMap<>();
        stackFlips.put(initialStack, 1);
        Queue<List<Integer>> queue = new ArrayDeque<>();
        queue.add(initialStack);
        while (!queue.isEmpty()) {
            List<Integer> stack = queue.remove();
            int flips = stackFlips.get(stack) + 1;
            for (int i = 2; i <= n; ++i) {
                List<Integer> flipped = flipStack(stack, i);
                if (stackFlips.putIfAbsent(flipped, flips) == null) {
                    queue.add(flipped);
                }
            }
        }
        return stackFlips.entrySet().stream().max(comparing(e -> e.getValue())).get();
    }
     
    public static void main(String[] args) {
        for (int i = 1; i <= 10; ++i) {
            Map.Entry<List<Integer>, Integer> result = pancake(i);
            System.out.printf("pancake(%s) = %s. Example: %s\n", i, result.getValue(), result.getKey());
        }
    }
}
Output:
pancake(1) = 1. Example: [1]
pancake(2) = 2. Example: [2, 1]
pancake(3) = 4. Example: [1, 3, 2]
pancake(4) = 5. Example: [2, 4, 1, 3]
pancake(5) = 6. Example: [4, 1, 3, 5, 2]
pancake(6) = 8. Example: [4, 6, 2, 5, 1, 3]
pancake(7) = 9. Example: [1, 4, 7, 3, 6, 2, 5]
pancake(8) = 10. Example: [4, 8, 6, 3, 1, 7, 2, 5]
pancake(9) = 11. Example: [8, 3, 5, 7, 9, 1, 6, 2, 4]

Julia

Translation of: Phix
function pancake(len)
    gap, gapsum, adj = 2, 2, -1
    while gapsum < len
        adj += 1
        gap = gap * 2 - 1
        gapsum += gap
    end
    return len + adj
end

for i in 1:25
    print("pancake(", lpad(i, 2), ") = ", rpad(pancake(i), 5)) 
    i % 5 == 0 && println()
end
Output:

Note that pancake(20) and above are guesswork

pancake( 1) = 0    pancake( 2) = 1    pancake( 3) = 3    pancake( 4) = 4    pancake( 5) = 5    
pancake( 6) = 7    pancake( 7) = 8    pancake( 8) = 9    pancake( 9) = 10   pancake(10) = 11
pancake(11) = 13   pancake(12) = 14   pancake(13) = 15   pancake(14) = 16   pancake(15) = 17
pancake(16) = 18   pancake(17) = 19   pancake(18) = 20   pancake(19) = 21   pancake(20) = 23
pancake(21) = 24   pancake(22) = 25   pancake(23) = 26   pancake(24) = 27   pancake(25) = 28

with examples

Exhaustive search, breadth first method.

function pancake(len)
    goalstack = collect(1:len)
    stacks, numstacks = Dict(goalstack => 0), 1
    newstacks = deepcopy(stacks)
    for i in 1:1000
        nextstacks = Dict()
        for (arr, steps) in newstacks, pos in 2:len
            newstack = vcat(reverse(arr[1:pos]), arr[pos+1:end])
            haskey(stacks, newstack) || (nextstacks[newstack] = i)
        end
        newstacks = nextstacks
        stacks = merge(stacks, newstacks)
        perms = length(stacks)
        perms == numstacks && return findmax(stacks)
        numstacks = perms
    end
end

for i in 1:10
    steps, example = pancake(i)
    println("pancake(", lpad(i, 2), ") = ", rpad(steps, 5), " example: ", example) 
end
Output:
pancake( 1) = 0     example: [1]
pancake( 2) = 1     example: [2, 1]
pancake( 3) = 3     example: [1, 3, 2]      
pancake( 4) = 4     example: [2, 4, 1, 3]   
pancake( 5) = 5     example: [5, 2, 4, 1, 3]
pancake( 6) = 7     example: [4, 6, 2, 5, 1, 3]
pancake( 7) = 8     example: [5, 1, 7, 3, 6, 2, 4]
pancake( 8) = 9     example: [6, 4, 8, 2, 5, 7, 1, 3]
pancake( 9) = 10    example: [8, 1, 4, 6, 9, 3, 7, 2, 5]
pancake(10) = 11    example: [1, 3, 8, 6, 9, 4, 2, 5, 10, 7]

Kotlin

Fast approximation

Translation of: Go – Original algorithm from Phix. The printing in main was adapted to use something more idiomatic.
fun pancake(n: Int): Int {
    var gap = 2
    var sum = 2
    var adj = -1
    while (sum < n) {
        adj++
        gap = gap * 2 - 1
        sum += gap
    }
    return n + adj
}

fun main() {
    (1 .. 20).map {"p(%2d) = %2d".format(it, pancake(it))}
    val lines = results.chunked(5).map { it.joinToString("  ") }
    lines.forEach { println(it) }
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5  
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11  
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17  
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  

Using exhaustive search

Using classic breadth-first search with running queue.

data class PancakeResult(val example: List<Int>, val depth: Int)

fun pancake(n: Int): PancakeResult {
  fun List<Int>.copyFlip(spatula: Int) = toMutableList().apply { subList(0, spatula).reverse() }
  val initialStack = List(n) { it + 1 }
  val stackFlips = mutableMapOf(initialStack to 1)
  val queue = ArrayDeque(listOf(initialStack))
  while (queue.isNotEmpty()) {
    val stack = queue.removeFirst()
    val flips = stackFlips[stack]!! + 1
    for (spatula in 2 .. n) {
      val flipped = stack.copyFlip(spatula)
      if (stackFlips.putIfAbsent(flipped, flips) == null) {
        queue.addLast(flipped)
      }
    }
  }
  return stackFlips.maxByOrNull { it.value }!!.run { PancakeResult(key, value) }
}

fun main() {
  for (i in 1 .. 10) {
    with (pancake(i)) { println("pancake($i) = $depth. Example: $example") }
  }
}
Output:
pancake(1) = 1. Example: [1]
pancake(2) = 2. Example: [2, 1]
pancake(3) = 4. Example: [1, 3, 2]
pancake(4) = 5. Example: [4, 2, 3, 1]
pancake(5) = 6. Example: [5, 1, 3, 2, 4]
pancake(6) = 8. Example: [5, 3, 6, 1, 4, 2]
pancake(7) = 9. Example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) = 10. Example: [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 11. Example: [4, 2, 3, 1, 5, 7, 9, 6, 8]
pancake(10) = 12. Example: [1, 3, 2, 4, 6, 8, 10, 5, 7, 9]

MAD

This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
            NORMAL MODE IS INTEGER
            VECTOR VALUES ROW = $5(2HP[,I2,4H] = ,I2,S2)*$
            
            INTERNAL FUNCTION(N)
            ENTRY TO P.
            GAP = 2
            ADJ = -1
            THROUGH LOOP, FOR SUM=2, GAP, SUM.GE.N
            ADJ = ADJ + 1
LOOP        GAP = GAP * 2 - 1
            FUNCTION RETURN N + ADJ
            END OF FUNCTION
            
            THROUGH OUTP, FOR R=1, 5, R.G.20
OUTP        PRINT FORMAT ROW, R,P.(R), R+1,P.(R+1), R+2,P.(R+2),
          0     R+3,P.(R+3), R+4,P.(R+4), R+5,P.(R+5)
            
            END OF PROGRAM
Output:
P[ 1] =  0  P[ 2] =  1  P[ 3] =  3  P[ 4] =  4  P[ 5] =  5
P[ 6] =  7  P[ 7] =  8  P[ 8] =  9  P[ 9] = 10  P[10] = 11
P[11] = 13  P[12] = 14  P[13] = 15  P[14] = 16  P[15] = 17
P[16] = 18  P[17] = 19  P[18] = 20  P[19] = 21  P[20] = 23

Nim

Maximum number of flips only

Translation of: Phix

This is the translation of the second version (5th dec 2020). It differs from the first version for p(19).

import strformat, strutils

func pancake(n: int): int =
  var
    gap, sumGaps = 2
    pg = 1
    adj = -1
  while sumGaps < n:
    inc adj
    inc pg, gap
    swap pg, gap
    inc sumGaps, gap
  result = n + adj

var line = ""
for n in 1..20:
  line.addSep("   ")
  line.add &"p({n:>2}) = {pancake(n):>2}"
  if n mod 5 == 0: (echo line; line.setLen(0))
Output:
p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  4   p( 5) =  5
p( 6) =  7   p( 7) =  8   p( 8) =  9   p( 9) = 10   p(10) = 11
p(11) = 13   p(12) = 14   p(13) = 15   p(14) = 16   p(15) = 17
p(16) = 18   p(17) = 19   p(18) = 20   p(19) = 22   p(20) = 23

Exhaustive search with examples

Translation of: Julia

We used a "TableRef" rather than a "Table" to optimize some assignments (Nim uses copy semantic when assigning). We also defined a function "partialReversed" rather than using the "reversed" function and a concatenation. These optimizations reduce the running time from about 21 seconds to about 17 seconds on our small laptop.

import sequtils, strformat, strutils, tables

type
  StepTable = TableRef[seq[int], int]
  Result = tuple[steps: int; example: seq[int]]

func findMax(t: StepTable): Result =
  result.steps = -1
  for example, steps in t.pairs:
    if steps > result.steps:
      result = (steps, example)

func partialReversed(arr: openArray[int]; pos: int): seq[int] =
  result.setlen(arr.len)
  for i in 0..<pos:
    result[i] = arr[pos - 1 - i]
  for i in pos..arr.high:
    result[i] = arr[i]

func pancake(n: int): Result =
  var goalStack = toSeq(1..n)
  var stacks, newStacks: StepTable = newTable({goalStack: 0})
  var numStacks = 1
  for i in 1..1000:
    var nextStacks = new(StepTable)
    for arr, steps in newStacks.pairs:
      for pos in 2..n:
        let newStack = partialReversed(arr, pos)
        if newStack notin stacks:
          nextStacks[newStack] = i
    newStacks = nextStacks
    for key, value in newStacks:
      stacks[key] = value
    let perms = stacks.len
    if perms == numStacks:
      return stacks.findMax()
    numStacks = perms

for n in 1..10:
  let (steps, example) = pancake(n)
  echo &"p({n:>2}) = {steps:>2}    example: ", example.join(", ")
Output:
p( 1) =  0    example: 1
p( 2) =  1    example: 2, 1
p( 3) =  3    example: 1, 3, 2
p( 4) =  4    example: 3, 1, 4, 2
p( 5) =  5    example: 2, 5, 3, 1, 4
p( 6) =  7    example: 5, 3, 6, 1, 4, 2
p( 7) =  8    example: 3, 6, 1, 4, 7, 2, 5
p( 8) =  9    example: 1, 7, 5, 3, 6, 8, 4, 2
p( 9) = 10    example: 8, 2, 7, 9, 5, 3, 1, 6, 4
p(10) = 11    example: 9, 6, 3, 5, 7, 4, 10, 1, 8, 2

ooRexx

Translation of: REXX
/*REXX program calculates/displays 20 pancake numbers (from 1 to 20,inclusive). */
ol=''
Do pcn=1 To 20
  ol=ol 'p('format(pcn,2)') ='format(pancake(pcn),3)' '
  If pcn//5=0 Then Do
    Say strip(ol)
    ol=''
    End
  End
Exit
/*------------------------------------------------------------------------------*/
pancake: Procedure
  Parse Arg n                            /* obtain  N                           */
  gap= 2                                 /* initialize the GAP.                 */
  sum= 2                                 /* initialize the SUM.                 */
  Do adj=0 While sum <n                  /* perform while  SUM is less than  N. */
    gap= gap*2 - 1                       /* calculate the GAP.                  */
    sum= sum + gap                       /* add the  GAP  to the  SUM.          */
    End   /*adj*/
  Return n +adj -1                       /* return an adjusted adjustment sum.  */
output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23

Show examples as required for this task

/* REXX Driver for pancake.test */
do n=2 To 10
  Call pancake n
  End
Exit
pancake: Procedure
/**********************************************************************
* REXX pancake.rex
* The task is to determine p(n) for n = 1 to 9,
* and for each show an example requiring p(n) flips.
* inspired by java and output like Phix
* Note: Using q~delete(1) to get the next candidate for flipping
* has dramatic performance consequences for large stacks.
* Therefore, I leave the queue alone and use a pointer (qp)
* 20230604 Walter Pachl
**********************************************************************/
Call time 'R'
parse arg n                          -- Number of pancakes
init=left('123456789abc',n)          -- ordered pancakes
Call o 'heureka' n
q=.queue~new                         -- implements the queue
qp=1
ex=0
q~append(init)
stackFlips.=-1                       -- initialize map
stackFlips.init=0                    -- stackFlips.v: number of flips
                                     -- from init to v
cnt.=0
cnt.1=1
max=0
Do while qp<=q~items                 -- as long we can flip
  s=q[qp]
  qp+=1                            -- get next element
  flips=stackFlips.s+1               -- flips for the successors
  cnt.flips=cnt.flips+1              -- count them
  If flips>max Then ex=0             -- a new maximum
  max=max(max,flips)
  Do i=2 To n                        -- process n-1 successors
    t=flip(s,i)                      -- one of them
    If stackFlips.t=-1 Then Do       -- not set so far
      stackFlips.t=flips             -- flips from init to t
      q~append(t)                    -- append it to the queue
      If ex<3 Then Do                -- show the forst 3 examples
        call o flips t
        If ex>=0 Then Do             -- record the data to be shown
          example=''                 -- as an example (see o2)
          Do While t<>''
            Parse Var t c +1 t
            Select
              When c='a' Then c=10
              When c='b' Then c=11
              When c='c' Then c=12
              Otherwise Nop
              End
            example=example||c||','
            End
          exf=flips
          example=strip(example,'T',',')
          End
        ex=ex+1
        End
      End
    End
  End
Call o 'max cnt.max:' max cnt.max
te=time('E')                         -- elaüsed time
te=strip(format(te,8,1))
Call o te 'seconds'
Call o ''
Call o2 'p('n') = 'exf', example: {'example'} (of' cnt.max', 'te's)'
Return

flip: Procedure
Parse Arg s,k                        -- cf. flipStack in java
Return substr(s,k,1)reverse(left(s,k-1))||substr(s,k+1)

o: -- investigation and debug output
Return
Say arg(1)
Return lineout('heureka.txt',arg(1))

o2: -- result to be shown in rosettacode
Say arg(1)
Call lineout 'heureka.out',arg(1)
Call lineout 'heureka.out'
Return
output   when using pancake_test.rex:
p(2) = 1, example: {2,1} (of 1, 0.0s)
p(3) = 3, example: {1,3,2} (of 1, 0.0s)
p(4) = 4, example: {3,1,4,2} (of 3, 0.0s)
p(5) = 5, example: {1,3,5,2,4} (of 20, 0.0s)
p(6) = 7, example: {4,6,2,5,1,3} (of 2, 0.0s)
p(7) = 8, example: {5,7,3,1,6,2,4} (of 35, 0.1s)
p(8) = 9, example: {6,8,4,2,3,1,7,5} (of 455, 1.1s)
p(9) = 10, example: {8,5,7,9,1,3,2,4,6} (of 5804, 15.4s)
p(10) = 11, example: {5,1,3,2,4,6,10,8,9,7} (of 73232, 208.0s)

Perl

use strict;
use warnings;
use feature 'say';

sub pancake {
    my($n) = @_;
    my ($gap, $sum, $adj) = (2, 2, -1);
    while ($sum < $n) { $sum += $gap = $gap * 2 - 1 and $adj++ }
    $n + $adj;
}

my $out;
$out .= sprintf "p(%2d) = %2d ", $_, pancake $_ for 1..20;
say $out =~ s/.{1,55}\K /\n/gr;

# Maximum number of flips plus examples using exhaustive search
sub pancake2 {
    my ($n) = @_;
    my $numStacks = 1;
    my @goalStack = 1 .. $n;
    my %newStacks = my %stacks = (join(' ',@goalStack), 0);
    for my $k (1..1000) {
        my %nextStacks;
        for my $pos (2..$n) {
            for my $key (keys %newStacks) {
                my @arr = split ' ', $key;
                my $cakes = join ' ', (reverse @arr[0..$pos-1]), @arr[$pos..$#arr];
                $nextStacks{$cakes} = $k unless $stacks{$cakes};
            }
        }
        %stacks = (%stacks, (%newStacks = %nextStacks));
        my $perms    = scalar %stacks;
        my %inverted = reverse %stacks;
        return $k-1, $inverted{(sort keys %inverted)[-1]} if $perms == $numStacks;
        $numStacks = $perms;
   }
}

say "\nThe maximum number of flips to sort a given number of elements is:";
for my $n (1..9) {
    my ($a,$b) = pancake2($n);
    say "pancake($n) = $a example: $b";
}
Output:
p( 1) =  0 p( 2) =  1 p( 3) =  3 p( 4) =  4 p( 5) =  5
p( 6) =  7 p( 7) =  8 p( 8) =  9 p( 9) = 10 p(10) = 11
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23

The maximum number of flips to sort a given number of elements is:
pancake(1) = 0 example: 1
pancake(2) = 1 example: 1 2
pancake(3) = 3 example: 1 3 2
pancake(4) = 4 example: 2 4 1 3
pancake(5) = 5 example: 5 3 1 4 2
pancake(6) = 7 example: 5 3 6 1 4 2
pancake(7) = 8 example: 5 7 3 4 1 6 2
pancake(8) = 9 example: 3 8 5 2 7 4 1 6
pancake(9) = 10 example: 7 5 9 6 2 4 1 8 3

Phix

fast estimate

Extra credit to anyone who can prove that this is in any way wrong?
(Apart from the lack of examples, that is)
The algorithm was freshly made up, from scratch, by yours truly.
It agrees with https://oeis.org/A058986/b058986.txt which would put p(20) as either 22 or 23.
(ie the p(20) shown below is actually pure guesswork, with a 50:50 chance of being correct)
Note that several other references/links disagree on p(17) and up.

with javascript_semantics
function pancake(integer n)
    integer gap = 2, sum_gaps = gap, adj = -1
    while sum_gaps<n do
        adj += 1
        gap = gap*2-1
        sum_gaps += gap
    end while
    n += adj
    return n
end function
sequence t = tagset(20),
         r = columnize({t,apply(t,pancake)}),
         p = apply(true,sprintf,{{"p(%2d) = %2d"},r})
printf(1,"%s\n",join_by(p,1,5))
Output:
p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  4   p( 5) =  5
p( 6) =  7   p( 7) =  8   p( 8) =  9   p( 9) = 10   p(10) = 11
p(11) = 13   p(12) = 14   p(13) = 15   p(14) = 16   p(15) = 17
p(16) = 18   p(17) = 19   p(18) = 20   p(19) = 21   p(20) = 23

vs. max() of ten runs each of pancake_sort(shuffle(tagset(n))), modified to return the number of flips it made:

p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  5   p( 5) =  6
p( 6) =  9   p( 7) = 10   p( 8) = 11   p( 9) = 12   p(10) = 15
p(11) = 16   p(12) = 17   p(13) = 20   p(14) = 22   p(15) = 25
p(16) = 28   p(17) = 28   p(18) = 31   p(19) = 33   p(20) = 34

Obviously the sort focuses on getting one pancake at a time into place, and therefore runs closer to 2n flips.

modified (5th Dec 2020)

It seems someone has recently modified A058986/b058986.txt so here is a matching modified version, which would make p(20) either 23 or 24.

with javascript_semantics
function pancake(integer n)
    integer gap = 2, pg = 1, sum_gaps = gap, adj = -1
    while sum_gaps<n do
        adj += 1
        {pg,gap} = {gap,gap+pg}
        sum_gaps += gap
    end while
    n += adj
    return n
end function
sequence t = tagset(20),
         r = columnize({t,apply(t,pancake)}),
         p = apply(true,sprintf,{{"p(%2d) = %2d"},r})
printf(1,"%s\n",join_by(p,1,5))
Output:
p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  4   p( 5) =  5
p( 6) =  7   p( 7) =  8   p( 8) =  9   p( 9) = 10   p(10) = 11
p(11) = 13   p(12) = 14   p(13) = 15   p(14) = 16   p(15) = 17
p(16) = 18   p(17) = 19   p(18) = 20   p(19) = 22   p(20) = 23

exhaustive search, with examples

Translation of: Julia
with javascript_semantics
function visitor(sequence stack, integer /*unused*/, sequence stacks)
    for pos=2 to length(stack) do
--  for pos=0 to length(stack)-2 do
        sequence newstack = reverse(stack[1..pos])&stack[pos+1..$]
--      sequence newstack = stack[1..pos]&reverse(stack[pos+1..$])
        if getd_index(newstack,stacks[1])=NULL then
            setd(newstack,0,stacks[$]) -- (next round)
            setd(newstack,0,stacks[1]) -- (the master)
        end if
    end for
    return 1
end function
 
function pancake(integer len)
    sequence goalstack = tagset(len),
             stacks = {new_dict({{goalstack,0}})}
    while true do
        stacks &= new_dict()
        -- add any flips of stacks[$-1]
        --   not already in stacks[1]
        --               to stacks[$]
        traverse_dict(visitor,stacks,stacks[$-1])
        if dict_size(stacks[$])=0 then exit end if
    end while
    sequence eg = getd_partial_key(0,stacks[$-1],true)
    integer sz = dict_size(stacks[$-1])
    papply(stacks,destroy_dict)
    return {length(stacks)-2,eg,sz}
end function
 
atom t0 = time()
for n=1 to 8 do -- (for <2s)
    {integer pn, sequence eg, integer sz} = pancake(n)
    printf(1,"p(%d) = %d, example: %v (of %,d, %s)\n",{n,pn,eg,sz,elapsed(time()-t0)})
end for
Output:

Note that we are only allowed to flip the left hand side, so [eg] we cannot solve p(3) by flipping the right hand pair.
lhs-only flips, the "of nn" shows how many unique stacks we found that required p(n) flips.

p(1) = 0, example: {1} (of 1, 0s)
p(2) = 1, example: {2,1} (of 1, 0.1s)
p(3) = 3, example: {1,3,2} (of 1, 0.1s)
p(4) = 4, example: {4,2,3,1} (of 3, 0.1s)
p(5) = 5, example: {5,3,1,4,2} (of 20, 0.1s)
p(6) = 7, example: {5,3,6,1,4,2} (of 2, 0.1s)
p(7) = 8, example: {7,3,1,5,2,6,4} (of 35, 0.2s)
p(8) = 9, example: {8,6,2,4,7,3,5,1} (of 455, 1.8s)
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (of 5,804, 19.6s)
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 7s)

After p(7), each subsequent p(n) takes about n times as long to complete.

rhs-only flips, using the two commented-out alternative lines in visitor(), and again showing the last one found, is more similar than I expected.

p(1) = 0, example: {1} (of 1, 0s)
p(2) = 1, example: {2,1} (of 1, 0.1s)
p(3) = 3, example: {2,1,3} (of 1, 0.1s)
p(4) = 4, example: {4,2,3,1} (of 3, 0.1s)
p(5) = 5, example: {5,3,1,4,2} (of 20, 0.1s)
p(6) = 7, example: {5,3,6,1,4,2} (of 2, 0.1s)
p(7) = 8, example: {7,2,4,1,6,3,5} (of 35, 0.3s)
p(8) = 9, example: {8,6,2,4,7,3,5,1} (of 455, 1.8s)
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (of 5,804, 19.2s)
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s)

Python

Translation of: Java
Works with: Python version 3.7
"""Pancake numbers. Requires Python>=3.7."""
import time

from collections import deque
from operator import itemgetter
from typing import Tuple

Pancakes = Tuple[int, ...]


def flip(pancakes: Pancakes, position: int) -> Pancakes:
    """Flip the stack of pancakes at the given position."""
    return tuple([*reversed(pancakes[:position]), *pancakes[position:]])


def pancake(n: int) -> Tuple[Pancakes, int]:
    """Return the nth pancake number."""
    init_stack = tuple(range(1, n + 1))
    stack_flips = {init_stack: 0}
    queue = deque([init_stack])

    while queue:
        stack = queue.popleft()
        flips = stack_flips[stack] + 1

        for i in range(2, n + 1):
            flipped = flip(stack, i)
            if flipped not in stack_flips:
                stack_flips[flipped] = flips
                queue.append(flipped)

    return max(stack_flips.items(), key=itemgetter(1))


if __name__ == "__main__":
    start = time.time()

    for n in range(1, 10):
        pancakes, p = pancake(n)
        print(f"pancake({n}) = {p:>2}. Example: {list(pancakes)}")

    print(f"\nTook {time.time() - start:.3} seconds.")
Output:
pancake(1) =  0. Example: [1]
pancake(2) =  1. Example: [2, 1]
pancake(3) =  3. Example: [1, 3, 2]
pancake(4) =  4. Example: [4, 2, 3, 1]
pancake(5) =  5. Example: [5, 1, 3, 2, 4]
pancake(6) =  7. Example: [5, 3, 6, 1, 4, 2]
pancake(7) =  8. Example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) =  9. Example: [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 10. Example: [4, 2, 3, 1, 5, 7, 9, 6, 8]

Took 2.89 seconds.

Raku

Maximum number of flips only

Translation of: C
# 20201110 Raku programming solution

sub pancake(\n) {
   my ($gap,$sum,$adj) = 2, 2, -1;
   while ($sum < n) { $sum += $gap = $gap * 2 - 1 and $adj++ }
   return n + $adj;
}

for (1..20).rotor(5) { say [~] @_».&{ sprintf "p(%2d) = %2d ",$_,pancake $_ } }
Output:
p( 1) =  0 p( 2) =  1 p( 3) =  3 p( 4) =  4 p( 5) =  5
p( 6) =  7 p( 7) =  8 p( 8) =  9 p( 9) = 10 p(10) = 11
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23

Maximum number of flips plus examples using exhaustive search

Translation of: Go
sub pancake(\n) {
   my @goalStack = (my \numStacks = $ = 1)..n ; 
   my %newStacks = my %stacks = @goalStack.Str, 0 ;
   for 1..1000 -> \k { 
      my %nextStacks = (); 
      for %newStacks.keys».split(' ') X 2..n -> (@arr, \pos) {
         given flat @arr[0..^pos].reverse, @arr[pos..*-1] {
            %nextStacks{$_.Str} = k unless %stacks{$_.Str}:exists
         }
      }
      %stacks ,= (%newStacks = %nextStacks);
      my $perms    = %stacks.elems;
      my %inverted = %stacks.antipairs;      # this causes loss on examples 
      my \max_key  = %inverted.keys.max;     # but not critical for our purpose
      $perms == numStacks ?? return %inverted{max_key}, k-1 !! numStacks=$perms
   }
   return '', 0
}

say "The maximum number of flips to sort a given number of elements is:";
for 1..9 -> $j { given pancake($j) { say "pancake($j) = $_[1] example: $_[0]" }}
Output:
The maximum number of flips to sort a given number of elements is:
pancake(1) = 0 example: 1
pancake(2) = 1 example: 2 1
pancake(3) = 3 example: 1 3 2
pancake(4) = 4 example: 2 4 1 3
pancake(5) = 5 example: 5 1 3 2 4
pancake(6) = 7 example: 5 3 6 1 4 2
pancake(7) = 8 example: 1 5 3 7 4 2 6
pancake(8) = 9 example: 6 1 8 3 5 7 2 4
pancake(9) = 10 example: 3 6 9 2 5 8 4 7 1

REXX

Translation of: Go
Translation of: Phix
/*REXX program calculates/displays 20 pancake numbers (from 1 to 20,inclusive). */
/* Gerard Schildberger's code reformatted and refurbished                       */
pad=copies(' ',10)                                               /*indentation. */
Say pad center('pancakes',10    ) center('pancake flips',15)     /*show the hdr.*/
Say pad center(''        ,10,"-") center('',15,"-")              /*  "   "  sep.*/
Do pcn=1 To 20
  Say pad center(pcn,10) center(pancake(pcn),15)                 /*index,flips. */
  End
Exit                                      /*stick a fork in it, we're all done. */
/*------------------------------------------------------------------------------*/
pancake: Procedure
  Parse Arg n                            /* obtain  N                           */
  gap= 2                                 /* initialize the GAP.                 */
  sum= 2                                 /* initialize the SUM.                 */
  Do adj=0 While sum <n                  /* perform while  SUM is less than  N. */
    gap= gap*2 - 1                       /* calculate the GAP.                  */
    sum= sum + gap                       /* add the  GAP  to the  SUM.          */
    End   /*adj*/
  Return n +adj -1                       /* return an adjusted adjustment sum.  */
output   when using the default inputs:
            pancakes   pancake flips
           ────────── ───────────────
               1             0
               2             1
               3             3
               4             4
               5             5
               6             7
               7             8
               8             9
               9            10
               10           11
               11           13
               12           14
               13           15
               14           16
               15           17
               16           18
               17           19
               18           20
               19           21
               20           23

Show examples as required for this task

/* REXX Driver for pancake.test */
do n=2 To 10
  Call pancake n
  End  
pancake: Procedure
/**********************************************************************
* REXX pancake.rex
* The task is to determine p(n) for n = 1 to 9,
* and for each show an example requiring p(n) flips.
* inspired by java and output like Phix
* 20230531 Walter Pachl
**********************************************************************/
Call time 'R'
parse arg n                          -- Number of pancakes
init=left('123456789abc',n)          -- ordered pancakes
Call o 'heureka' n
q.=0                                 -- implements the queue
qp=1
ex=0
call qadd init
stackFlips.=-1                       -- initialize map
stackFlips.init=0                    -- stackFlips.v: number of flips
                                     -- from init to v
cnt.=0
cnt.1=1
max=0
Do while qp<=q.0                     -- as long we can flip
  s=qget()                           -- get head of queue
  flips=stackFlips.s+1               -- flips for the successors
  cnt.flips=cnt.flips+1              -- count them
  If flips>max Then ex=0             -- a new maximum
  max=max(max,flips)
  Do i=2 To n                        -- process n-1 successors
    t=flip(s,i)                      -- one of them
    If stackFlips.t=-1 Then Do       -- not set so far
      stackFlips.t=flips             -- flips from init to t
      Call qadd t                    -- append it to the queue
      If ex<3 Then Do                -- show the first 3 examples
        call o flips t
        If ex>=0 Then Do             -- record the data to be shown
          example=''                 -- as an example (see o2)
          Do While t<>''
            Parse Var t c +1 t
            Select
              When c='a' Then c=10
              When c='b' Then c=11
              When c='c' Then c=12
              Otherwise Nop
              End
            example=example||c||','
            End
          exf=flips
          example=strip(example,'T',',')
          End
        ex=ex+1
        End
      End
    End
  End
Call o 'max cnt.max:' max cnt.max
te=time('E')                         -- elapsed time
te=strip(format(te,8,1))
Call o te 'seconds'
Call o ''
Call o2 'p('n') = 'exf', example: {'example'} (of' cnt.max', 'te's)'
Return

flip: Procedure
Parse Arg s,k                        -- cf. flipStack in java
Return substr(s,k,1)reverse(left(s,k-1))||substr(s,k+1)

qadd:                                -- add an element to the queue
Parse Arg e
z=q.0+1
q.z=e
q.0=z
Return

qget:                                -- get top element from the queue
e=q.qp                               -- and remove it from the queue
qp=qp+1
Return e

o: -- investigation and debug output
Return
Say arg(1)
Return lineout('heureka.txt',arg(1))

o2: -- result to be shown in rosettacode
Say arg(1)
Call lineout 'heureka.out',arg(1)
Call lineout 'heureka.out'
Return
output   when using pancake_test.rex:
p(2) = 1, example: {2,1} (of 1, 0.0s)
p(3) = 3, example: {1,3,2} (of 1, 0.0s)
p(4) = 4, example: {3,1,4,2} (of 3, 0.0s)
p(5) = 5, example: {1,3,5,2,4} (of 20, 0.0s)
p(6) = 7, example: {4,6,2,5,1,3} (of 2, 0.0s)
p(7) = 8, example: {5,7,3,1,6,2,4} (of 35, 0.1s)
p(8) = 9, example: {6,8,4,2,3,1,7,5} (of 455, 1.1s)
p(9) = 10, example: {8,5,7,9,1,3,2,4,6} (of 5804, 11.6s)
p(10) = 11, example: {5,1,3,2,4,6,10,8,9,7} (of 73232, 238.5s)

Ring

This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C

Does not show examples requiring p(n) flips, since that is beyond the capabilities of Ring.

for n = 1 to 9 
    see "p(" + n + ") = " + pancake(n) + nl
next
return 0

func pancake(n)
     gap = 2
     sum = 2
     adj = -1;
     while (sum < n)
            adj = adj + 1
            gap = gap * 2 - 1
            sum = sum + gap
     end
     return n + adj

Output:

p(1) = 0
p(2) = 1
p(3) = 3
p(4) = 4
p(5) = 5
p(6) = 7
p(7) = 8
p(8) = 9
p(9) = 10

Ruby

This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
def pancake(n)
    gap = 2
    sum = 2
    adj = -1
    while sum < n
        adj = adj + 1
        gap = gap * 2 - 1
        sum = sum + gap
    end
    return n + adj
end

for i in 0 .. 3
    for j in 1 .. 5
        n = i * 5 + j
        print "p(%2d) = %2d  " % [n, pancake(n)]
    end
    print "\n"
end
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23

Rust

Translation of: C
fn pancake(n: i32) -> i32 {
    let mut gap = 2;
    let mut sum = 2;
    let mut adj = -1;

    while sum < n {
        adj += 1;
        gap = gap * 2 - 1;
        sum += gap;
    }

    n + adj
}

fn main() {
    for i in 0..4 {
        for j in 1..6 {
            let n = i * 5 + j;
            print!("p({:2}) = {:2}  ", n, pancake(n));
        }
        println!();
    }
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5  
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11  
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17  
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  

Scala

Translation of: C
object Pancake {
  def pancake(n: Int): Int = {
    var gap = 2
    var sum = 2
    var adj = -1

    while (sum < n) {
      adj += 1
      gap = 2 * gap - 1
      sum += gap
    }

    n + adj
  }

  def main(args: Array[String]): Unit = {
    for (i <- 0 until 4) {
      for (j <- 1 until 6) {
        val n = 5 * i + j
        print(f"p($n%2d) = ${pancake(n)}%2d  ")
      }
      println()
    }
  }
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5  
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11  
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17  
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  



Wren

Maximum number of flips only

Translation of: Phix
Library: Wren-fmt

Well, it's hard to believe it can be as simple as this but Pete's algorithm does at least give the same answers as the OEIS sequence for n <= 19 which is usually taken as the authority on these matters.

Clearly, for non-trivial 'n', the number of flips required for the pancake sorting task will generally be more as no attempt is being made there to minimize the number of flips, just to get the data into sorted order.

import "./fmt" for Fmt

var pancake = Fn.new { |n|
    var gap = 2
    var sum = 2
    var adj = -1
    while (sum < n) {
        adj = adj + 1
        gap = gap*2 - 1
        sum = sum + gap
    }
    return n + adj
}

for (i in 0..3) {
    for (j in 1..5) {
        var n = i*5 + j
        Fmt.write("p($2d) = $2d  ", n, pancake.call(n))
    }
    System.print()
}
Output:
p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5  
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11  
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17  
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  

Maximum number of flips plus examples using exhaustive search

Translation of: Julia

Takes a while to process pancake(9) though not too bad for the Wren interpreter particularly as maps don't support lists as keys and we therefore have to convert them to/from strings which is an expensive operation.

Note that map iteration order is undefined in Wren and so the examples are (in effect) randomly chosen from those available.

import "./fmt" for Fmt

// Converts a string of the form "[1, 2]" into a list: [1, 2]
var asList = Fn.new { |s|
    var split = s[1..-2].split(", ")
    return split.map { |n| Num.fromString(n) }.toList
}

// Merges two maps into one. If the same key is present in both maps
// its value will be the one in the second map.
var mergeMaps = Fn.new { |m1, m2|
    var m3 = {}
    for (key in m1.keys) m3[key] = m1[key]
    for (key in m2.keys) m3[key] = m2[key]
    return m3
}

// Finds the maximum value in 'dict' and returns the first key
// it finds (iteration order is undefined) with that value. 
var findMax = Fn.new { |dict|
    var max = -1
    var maxKey = null
    for (me in dict) {
        if (me.value > max) {
            max = me.value
            maxKey = me.key
        }
    }
    return maxKey
}
   
var pancake = Fn.new { |len|
    var numStacks = 1
    var goalStack = (1..len).toList.toString
    var stacks = {goalStack: 0}
    var newStacks = {goalStack: 0}
    for (i in 1..1000) {
        var nextStacks = {}
        for (key in newStacks.keys) {
            var arr = asList.call(key)
            var pos = 2
            while (pos <= len) {
                var newStack = (arr[pos-1..0] + arr[pos..-1]).toString
                if (!stacks.containsKey(newStack)) nextStacks[newStack] = i
                pos = pos + 1
            }
        }
        newStacks = nextStacks
        stacks = mergeMaps.call(stacks, newStacks)
        var perms = stacks.count
        if (perms == numStacks) return [findMax.call(stacks), i - 1]
        numStacks = perms
    }
}

var start = System.clock
System.print("The maximum number of flips to sort a given number of elements is:")
for (i in 1..9) {
    var res = pancake.call(i)
    var example = res[0]
    var steps = res[1]
    Fmt.print("pancake($d) = $-2d  example: $n", i, steps, example)
}
System.print("\nTook %(System.clock - start) seconds.")
Output:
The maximum number of flips to sort a given number of elements is:
pancake(1) = 0   example: [1]
pancake(2) = 1   example: [2, 1]
pancake(3) = 3   example: [1, 3, 2]
pancake(4) = 4   example: [3, 1, 4, 2]
pancake(5) = 5   example: [5, 1, 3, 2, 4]
pancake(6) = 7   example: [5, 3, 6, 1, 4, 2]
pancake(7) = 8   example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) = 9   example: [6, 1, 3, 8, 2, 5, 7, 4]
pancake(9) = 10  example: [5, 8, 6, 1, 4, 2, 7, 9, 3]

Took 67.792918 seconds.