binary fractions

I always enjoy teaching my origami class.  Last week things got a little mathy.  I learned the following trick from Tom Hull's excellent book, Project Origami, which I highly recommend.

Here's the problem:  say you have a piece of paper and you want to divide it into \( n \) equal subdivisions.  If \( n \) is a power of \( 2 \), then no problem; you've been doing this since you were a kid (just fold in half repeatedly).  Since every positive integer \( n \) may be written in the form \( n = 2^r m \), where \( m \) is odd, we need only figure out how to do this for odd numbers of subdivisions.

There's an interesting iterative method to find an approximate solution to this (more on approximate vs. exact later), and it goes like this.  Make an initial guess of what you think \( \frac{1}{n} \) is and make a small pinch in your paper at \( \frac{1}{n} \) from the left edge.  Then the right side of the paper has an estimate of \( \frac{n-1}{n} \).  Since \( n \) is odd, \( n-1 \) is even, so you can fold that in half (just make a pinch at that point).  Now, one of two things happens:  either \( \frac{n-1}{2} \) is even or it is odd.  In the former case, you have an even number of \( \frac{1}{n}\textrm{'s} \) to the right of your new mark; in the latter case you have an even number of these to the left.  Fold the appropriate side in half (again, just pinch your marks).  Continue this process until you get back near to your initial guess of \( \frac{1}{n} \).  You probably won't be exactly at your initial guess, but if you're at all good at estimation you'll be close.  Run through this process again.  When you get back to what you think \( \frac{1}{n} \) is the second time you may stop.  That point is very close to where \( \frac{1}{n} \) actually is, and if \( n \) is large enough will be the same as where you wound up after running this algorithm only once. 

Here's the sequence of folds for \( n=5\).  Note that mark number \( 5 \) is my updated estimate for \( \frac{1}{5} \), and that mark number \( 9 \) is the result of two passes through the algorithm.  The last mark is virtually indistinguishable from mark number \( 5 \).

The situation for \( n=7 \) is a little different.  Here is the picture of one pass through the algorithm.

As you can see, this is a little different than the \( n=5 \) case.  Notice that I only made marks at my guess for \( \frac{1}{7} \), at \( \frac{4}{7} \), and \( \frac{2}{7} \) before getting back to an estimate of \( \frac{1}{7} \) (which turned out to be very close to my initial guess).  There's some interesting number theory going on with that, but I'll skip that for now.

Finally, here's what happens after one pass through for \( n=11 \).

In this case, I made a mark at all \( 10 \) of the subdivisions, coming back to a place near my initial guess.  Running through the algorithm again would get me back so close to mark number \( 11 \) that I didn't bother to do it. 

Now, here's something we can do.  At each stage we do one of two things: fold the right edge to a point in the interior or fold the left edge to a point in the interior.  If we keep track of the sequence of folds we get the following.

\( \frac{1}{3} \quad RLRLRLRL\dots \)

\( \frac{1}{5} \quad RRLLRRLLRRLL\dots \)

\( \frac{1}{7} \quad  RLLRLLRLL\dots  \)

\( \frac{1}{9} \quad  RRRLLLRRRLLL\dots \)

\( \frac{1}{11} \quad  RLRRRLRLLL\dots  \)

There's a connection with this and writing the fraction \( \frac{1}{n} \) in binary.  We all know from grade school that \( \frac{1}{3} = 0.3333\dots \) and \( \frac{1}{7} = 0.142857\dots \).  Of course, what this really means is that

\( \frac{1}{3} = \frac{3}{10} + \frac{3}{100} + \frac{3}{1000} +\cdots + \frac{3}{10^r} +\cdots \)

\( \frac{1}{7} = \frac{1}{10} + \frac{4}{100} + \frac{2}{1000} + \frac{8}{10^4} + \frac{5}{10^5} + \frac{7}{10^6} + \cdots \)

But there's nothing special about \( 10 \), except that we have \( 10 \) fingers.  We could just as well write these fractions with powers of \( 2 \) in the denominators:

\( \frac{1}{3} = \frac{0}{2} + \frac{1}{2^2} + \frac{0}{2^3} + \frac{1}{2^4} +\cdots \)

\( \frac{1}{5} = \frac{0}{2} + \frac{0}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \frac{0}{2^5} + \frac{0}{2^6} + \cdots \)

\( \frac{1}{7} = \frac{0}{2} + \frac{0}{2^2} + \frac{1}{2^3} + \frac{0}{2^4} + \frac{0}{2^5} + \frac{1}{2^6} +\cdots \)

\( \frac{1}{9} = \frac{0}{2} + \frac{0}{2^2} + \frac{0}{2^3} + \frac{1}{2^4} + \frac{1}{2^5} + \frac{1}{2^6} + \cdots \)

and so on.  Note that for any odd \( n \), we'll always get a repeating "decimal" expansion this way.

Now look closely.  If we use the following dictionary: \( R = 1, L = 0 \) and read from right to left beginning at the last digit in the repeating "chunk" we see that the fold sequence tells us the binary expansion of \( \frac{1}{n} \).  For example, \( \frac{1}{5} = 0.\overline{0011} \) and the fold sequence is \( RRLL \).  Since the fold sequence for \( n=11 \) is \( RLRRRLRLLL \), we find that

\( \frac{1}{11} = \frac{0}{2} + \frac{0}{2^2} + \frac{0}{2^3} + \frac{1}{2^4} + \frac{0}{2^5} + \frac{1}{2^6} + \frac{1}{2^7} + \frac{1}{2^8} + \frac{0}{2^9} + \frac{1}{2^{10}} + \cdots \)

This is a fun fact.  So, for any odd \( n \), if you want to know the binary expansion of \( \frac{1}{n} \), you only need to figure out the fold sequence, and really, you don't even need a strip of paper to do it.  You only need to think about the fold sequence; maybe use a pen and paper to keep track.  For example, if \( n = 2^r + 1 \) for some \( r \), then the fold sequence is obviously

\( \underbrace{RRR\cdots R}_\text{\( r \)}\underbrace{LLL\cdots L}_\text{\( r \)} \)

and so

\( \frac{1}{2^r + 1} = \frac{0}{2} + \cdots + \frac{0}{2^r} + \frac{1}{2^{r+1}} +\cdots + \frac{1}{2^{2r}} \)

Finally, a word about the iterative process.  There are exact methods to fold a strip of paper into exact \( n \)ths, but they are (a) very complicated, and (b) not more accurate in practice.  Indeed, it is difficult to fold exactly, and errors inevitably creep in.  This algorithm works just as well and is much easier to implement.

Happy folding!