title: Folding paper strip and generate numbers while unfolding
body: <p>I have an assignment question that I am struggling with and need some direction to solve.
  Suppose i have a strip of paper and i fold it from the center such that the left half goes behind the right half. Then i number the folded peices in sequence i get the numbers when i unfold as follows.
  1 : 2</p>
  
  <p>If i fold twice i get the numbers when unfolded as follows
  1 : 4 : 3 : 2</p>
  
  <p>if I fold thrice i get as follows
  1 8 5 4 3 6 7 2</p>
  
  <p>I want to generate the array of numbers when I fold it n times. so if i fold it for example 25 times i will get 2^25 numbers in similar sequence.</p>
  
  <p>These are the observations i made</p>
  
  <ul>
  <li><p>the first and last numbers are always 1 and 2.</p></li>
  <li><p>the middle two numbers are always 4 and 3</p></li>
  <li><p>the number at index 1 is largest number and number at second last location is second largest number.</p></li>
  <li><p>It looks like a preorder traversal of binary search tree but I dont know how that helps.</p></li>
  <li>I tried to construct binary tree from the preorder and then convert it to inorder assuming that I can reverse this process to get the same series and I was wrong about it.</li>
  </ul>
  
  <p><strong>EDIT</strong> : For searching an element in this generated array I can do a sequential search which will be O(n) efficient. But I realise there has to be a much faster way to search for a number in this series. </p>
  
  <p>I cannot do binary search because this is not sorted and there are over a billion numbers when 25+ foldings are done. </p>
  
  <p>What kind of search tactics can i use to find a number and its index? </p>
  
  <p>This was one of the reasons I wanted to convert it into a binary search tree which will have log(n) search efficiency.</p>
  
  <p><strong>EDIT 2:</strong> I tried the table folding algorithm as suggested by one of the answers and it is not memory efficient. I cannot store over a billion numbers in my memory so there has to be a way to find a numbers index without actually creating the array of numbers.</p>