2009-01-10

The Paper Dragon

Bengt has a long strip of paper. He puts it on the table, and folds it in half. He lifts up the right hand end, folds it over and puts it on the left hand end. Then he repeats that same procedure several times. When he unfolds the paper, it has a funny curly pattern, which supposedly looks like a dragon. But Bengt is a true scientist and is not content to note that the pattern looks nice. He wants a formula.
If you call a fold in one direction 0 and in the other direction 1, the result is
0010011000110110001001110011011...
  1. Find a way to reproduce the sequence mathematically.
  2. Find a recursive formula that describes it, that is, the folding direction as a function of the direction of one or more previous folds.
  3. Find a non-recursive formula, that is, the folding direction as a function of only the number of fold.