Pancake numbers

Pancake numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 rumination. 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.

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

F#

<lang fsharp> // Pancake numbers. Nigel Galloway: Octber 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
                                                      |_->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 (set1..z) 1..z

[1..9]|>List.iter(fun n->printf "%d->%d " n (pKake n)); printfn "" </lang>

Output:

1->0 2->1 3->3 4->4 5->5 6->7 7->8 8->9 9->10

Phix

Extra credit to anyone who can prove that this is in any way wrong?
(The algorithm is freshly made up today, from scratch, by yours truly. p(20)=23 is obviously a bit of a guess.) <lang Phix>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))</lang>

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.

REXX

<lang rexx>/*REXX program calculates/displays N pancake numbers, or a range of pancake numbers.*/ parse arg LO HI . if LO== & HI=="" then do; LO= 1; HI= 20; end /*Not specified? Then use the default.*/ if LO== | LO=="," then LO= 1 /* " " " " " " */ if HI== | HI=="," then HI= LO /* " " " " " " */ a= -1 /*initialize the increase for each row.*/

   pad= center(,         10)

say pad center('pancakes', 10 ) center('pancake flips', 15 ) say pad center( , 10, "─") center(, 15, "─")

1. = 0 /*the number of pancake flips (so far).*/

    do j=1  until #>=HI
    if j==1  then do;   say pad center(j, 10)  center(#, 15);   #= # + 1
                        iterate                 /* [↑]  handle case for one pancake.   */
                  end
    a= a + 2                                    /*bump the width for this triangle row.*/
             do k=j  for a  until #==HI
             #= # + 1                           /*bump the number of pancakes.         */
             if k>=LO  then say pad  center(#, 10)  center(k-1, 15)
             end   /*k*/
    j= k                                        /*will be using K+1 as start of row #. */
    end            /*j*/                        /*stick a fork in it,  we're all done. */</lang>

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           21
               19           22
               20           23