3
$\begingroup$

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

  • 0
    Thanks! It's nice to see that Flickr photo.2012-09-06

3 Answers 3

2

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.

  • 0
    @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.2012-09-06
1

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?

  • 0
    This is a case where I wish I could accept two answers!2012-09-09
0

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.

  • 0
    Thanks for the comment! What I'm most curious about are the diagonals and the middle vertical features.2012-09-06