Wocky said:
mollwollfumble said:
I now have a lower limit on pancake numbers.
P(4) = 4
P(5) >= 4
P(10) >= 9
P(20) >= 16
P(30) >= 24
Those are based on the maximum number of permutations than can be generated by N flips of X pancakes.
I get:
P(4) = 4
P(5) = 5
P(10) = 11
21 <= P(20) <= 32
32 <= P(30) <= 49
But I may be wrong.
You’re better than me. Overnight I figured out that, because each pancake flip can bring only two adjacent pancakes together, and because in the original stack for X>2 it is always possible to have no two finally-adjacent pancakes initially-together, P(X) >= X-1 for all X.
Somewhat annoying, but potentially useful, is that flipping 3412 to get a final 1234 requires four flips. Not only does 3412 contain two finally-adjacent pancakes but it also cannot be obtained by inserting a single pancake anywhere in the stack 213. The stack 213 is the only stack of three pancakes that requires three flips to get 123. That makes it more difficult to get P(X) from P(X-1).
I can see three possible approaches to calculating P(20) by computer, none seems to be particularly easy.
1. Run it like a “sieve of Eratosthenes”. Starting from all the pancakes in final order 1 2 3 … 20 perform pancake flips in turn until all possible permutations are covered. The problem with that is that storing all possible permutations (20!) requires at least 17*4*20! bits of data. That’s 41 million terrabytes of data, too big. As more flips are done but before 20 are done, this can be used to slowly raise the minimum value of P(20). Hold on, perhaps I can reduce that to 20! bits of data, 600 petabytes of data, still too big.
2. Choose a “random” starting permutation from a set of “difficult ones” and calculate how many permutations are needed to create it. This is very much slower than the first approach unless the set of “difficult ones” can be reduced to something small, and I don’t see how it can be. This gives a very rapid calculation of a lower limit on P(20). A lower limit on P(X) obtained this way will usually be the actual value of P(X), but proving that for any given X would be very difficult.
3. Working from P(19) insert an unknown size “y” pancake into the stack and reproduce the flips on that stack as if it had 19 pancakes, with “y” remaining unknown. After the flips the pancake “y” will be in a specific position (actually two or more positions as the method bifocates) and that position suffices (ie. two or more positions suffice) to determine the value (values) of “y”. This finds all permutations of 20 pancakes that can be flipped in the same number of flips as 19 pancakes. This approach is slower than the first approach and faster than the second approach, except that it still doesn’t decide between P(20) = P(19) +1 and P(20) = P(19) + 2.