Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I wrote a program to visualize binary expansions of fractions in the form of a grid. Each row is one fraction; for instance the third row is 1/3 = 0.010101... The digits are color-coded, gray for 1 and blue for 0.

demo grid

When I made a big version of the grid (below) with many more fractions and one pixel per digit, I was surprised at how many patterns I saw. It's not shocking that there are prominent horizontal stripes around powers of 2, but there are also diagonal "stripes" and near-vertical structures. I can even convince myself there are various thick horizontal bands with different proportions of ones and zeros.

This feels like a pretty natural construction, so it must have been done before. Regardless, I'd be interested in any pointers or explanations of the stripes I'm seeing.

enter image description here

share|improve this question
    
It is a butiful picture. A similar attempt was made at:flickr.com/photos/22456939@N05/3256475254 –  Emmad Kareem Sep 6 '12 at 2:12
    
Thanks! It's nice to see that Flickr photo. –  Martin M. W. Sep 6 '12 at 2:35

3 Answers 3

up vote 1 down vote accepted

The dark blue horizontal stripes are caused by termination. They are at $\frac 1{2^n}$ which has all zeros after some point. Just above $\frac 1{2^n}$, you have lots of zeros in the repeat of $\frac 1{2^n-1}$ and still pretty many for numbers a little further away. The blue and gray stripes very near the left edge are the leading $0$ bits and $1$ bit. All the fractions between $\frac 1{2^n+1}$ and $\frac 1{2^{n+1}}$ have the same leading bit. I don't understand the diagonal stripes, maybe they are an artifact of the square pixels. I wonder if the vertical stripes are at positions that have lots of divisors, where you have extra repeats coming, but that is just a guess. Maybe you could look.

share|improve this answer
    
Yes, I'm most interested in the vertical stripes (in the middle) and the diagonals. The diagonals are pretty robust to different ways of drawing the picture, different bases, etc. (and you can see some less prominent ones at different angles) so I don't think they're artifacts. The positions of the vertical stripes are a bit hard to pin down (they drift slowly with the log of the vertical position) but a couple do start roughly at prime powers (361, 243). But why those prime powers? And why would you get dark stripes as opposed to light ones? –  Martin M. W. Sep 6 '12 at 2:31
1  
@MartinM.W.: In base $2$, the last bit of a repeat is always $1$ for fractions of the form $\frac 1n$. The start of the next repeat starts with a block of $\lceil \log_2 n \rceil 0$'s. I was guessing that it is not prime powers, but highly divisible numbers like $240, 360$. Lots of numbers may have repeats that end there, then you get the block of zeros. –  Ross Millikan Sep 6 '12 at 2:39
    
That makes sense. By the same token, maybe it's not uncommon for the repeats of $1/n$ to end roughly around the $n$th position. (For instance, a prime $p$ has a period that divides $p-1$ I think?) Perhaps that might explain the diagonals. –  Martin M. W. Sep 6 '12 at 2:57
    
@MartinM.W.: you are right, the period of a prime divides $p-1$. Generally, the period of n divides $\phi(n)$, Euler's totient function. –  Ross Millikan Sep 6 '12 at 3:25

The diagonals can be explained as a "reflection" of the dark vertical band to the far left, which is repeated to the right because each binary fraction is periodic.

When $n$ is odd, the expansion of $\frac 1n$ has a period that divides $\varphi(n)$. (Namely, then $2$ and $n$ are coprime, so the period of $\frac 1n$ is the period of $1, 2, 4, \ldots 2^i \ldots$ modulo $n$, which is the order or a subgroup of the multiplicative group modulo $n$ generated by $2$). Thus the pronounced diagonals in the graph of the totient function become darkish diagonals in your picture.

The origin of the vertical stripes is less clear to me. Have you measured the positions the more pronounced of them occur at?

share|improve this answer
    
Thanks, the pointer to the totient function graph explains a lot! As for the positions of the vertical stripes, see the comment to Ross's answer: they seem to be at numbers with many divisors. –  Martin M. W. Sep 6 '12 at 22:35
    
This is a case where I wish I could accept two answers! –  Martin M. W. Sep 9 '12 at 16:22

I think part of the explanation is that regardless of base, every rational number can be represented as an eventually repeating decimal. The repeating numeric pattern contributes greatly to some of the patterns you are seeing. If you consider the pattern 0000...., then numbers like $1/4=0.010000000....$ will give you the long horizontal lines. In base 2, you will notice this for numbers like $1/2,1/4,1/8,\ldots$ (can you work out why?). The vertical lines on the left hand side of your grid get wider as your numbers get smaller.

share|improve this answer
    
Thanks for the comment! What I'm most curious about are the diagonals and the middle vertical features. –  Martin M. W. Sep 6 '12 at 2:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.