On Jan 26, 2006, at 8:35 AM, Andrew Dudzik wrote:

>>
>> I think there is still some interesting math to pull out of this
>> problem. For example, Andrew Dudzik ponders: "There are never two
>> sequences that give the same perm. Does anybody know why this is?
>> Seems like an interesting math problem." Myself, I wonder if he's
>> right.
>>
>
> I think that this is true, and that it follows from Bill Dolinar's  
> solution
> for check_fold--the last fold is always uniquely determined by  
> picking some
> x and y coordinates and looking at the numbers on the top and  
> bottom of the
> stack--if, say, 4 and 7 are on opposite sides of the folded paper,  
> they must
> have been in the same sheet one fold ago--the direction of this  
> fold is
> determined by the relative orientation of 4 and 7 in the original,  
> unfolded
> paper.
>
> Since there is only ever one possible direction to unfold, there  
> can only be
> at most one sequence of unfolds that gives the desired 1--n^2 pattern.
> Hence there is at most one sequence of folds that produces a given
> permutation.

When I was testing my solution for check_fold I found that it was  
very fast at going through the unfolding.  I ran a test on the  
unfolding the 2048x2048 data and found that I could run unfold a  
thousand times in about 2.5 seconds.  Quite the difference compared  
to fold running once in about 160 seconds.  With the unfold being so  
fast, one would think there must be some way to speed up folding  
considerably.  I spent some time trying to find a pattern and came up  
with formulas for the first fold where given the array index it gave  
the new index, but when considering layers as well on the second fold  
it made my head spin.  Thinking about it though, in the algorithm to  
unfold you only have to consider two elements of the array each time  
you unfold.  For folding you have to consider every element of the  
array for each fold.

Bill