up to John Chew's Math Files

Flipping Pancakes

If you have a stack of n pancakes in random order and want to sort them from smallest to largest, and the only tool you have is a pair of tongs with which to "flip" (reverse the order of) the top k pancakes, what's the largest number of flips it may take?

I have a C program that calculates f(m,n), the number of permutations that require m prefix reversals to transform into the identity transformation. (The answer to the pancake question is the largest m for which f(m,n) is nonzero.)

The program works by brute force, examining each of the n! permutations, and requires 2*n! bits of space to run in (all of which ought to be real memory, to avoid excessive disk thrashing) and O(n!) running time.

I've run the program for all values of n up to 12, and am looking for a machine that can run n=13. This will take a little less than 1.5 gigabytes of memory, and several hours or a few days on a fast machine. If you're willing to run the program, I'll be more than happy to give you credit in the short paper that I am writing on this subject.

The program can be downloaded from this link. Compile it with as much optimization as you can, and make sure your compiler is set to understand 'long long' as a 64-bit integer type. Run the program with the command line argument "9" to test it. On a fast machine at my department, it takes about six seconds to generate the following output:

n=9 m=0 count=1
n=9 m=1 count=8
n=9 m=2 count=56
n=9 m=3 count=391
n=9 m=4 count=2278
n=9 m=5 count=10666
n=9 m=6 count=38015
n=9 m=7 count=93585
n=9 m=8 count=132697
n=9 m=9 count=79379
n=9 m=10 count=5804

Check that your output matches, and that the running time is reasonable. Then run the program again with the command line argument "13", preferably nohup'd and tee'd into a file (assuming you're on a Unix system, use appropriate measures to prevent the system from killing your job and to capture the output under another operating system). The first few lines of output should theoretically read:

n=13 m=0 count=1
n=13 m=1 count=12
n=13 m=2 count=132
n=13 m=3 count=1451

and they should come out very quickly. The numbers will come out more slowly as they increase, and the last value of m will probably be 15. Please e-mail me the output of the program, to poslfit@gmail.com If the program dies or is killed before it finishes, I will of course be interested in partial results.