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.

First post, so please let me know if I'm doing something wrong or if this question does not belong here.

I have been toying with java to visualize an interesting 2D binary array I thought of today in my math class. My thought was to start with one origin cell, and set all cells in an infinite grid equal to 1. Then, starting with the 8 cells surrounding the origin and moving outward, each cell would be evaluated by the following rule:

-If the cell at (x,y) == 1, then any cell at (n*x,n*y) = 0, for all positive integers n > 1

Basically I was thinking that if (1,0) was on, then all of the other cells behind it - (2,0), (3,0), etc... would be "in it's shadow" and therefore equal to zero. I figured the result would have some significance with prime numbers, and it did.

I wrote a program to plot all the cells in the 4th quadrant, up to about x=2000, y=1000 and took screenshots at various zoom levels. Here are the results:

enter image description here

enter image description here

The top left cell (0,0) is arbitrarily set to 1. Here's the algorithm:

    boolean [][] grid = new boolean[height][width];

    for(int x=0; x<width; x++)
    {
      for(int y=0; y<height; y++)
      {
          grid[x][y] = true;
      }
    }

    for(int x=0; x<width; x++)
    {
      for(int y=0; y<height; y++)
      {
          if(grid[x][y])
          {
              int xt = 2*x;
              int yt = 2*y;

              while((xt < width && yt < height) && (xt != 0 || yt != 0))
              {
                  grid[xt][yt] = false;

                  xt += x;
                  yt += y;
              }
          }
      }
    }

On a large scale, it looks somewhat uniform, but on a small scale it looks random (or at least I can't see the pattern).

Here's my questions:

1 - Has this "function" been researched before? It seems interesting to me, but I can't find anything online about it.

2 - Where is this randomness coming from? The code is so simple, but the result looks very complex.

3 - Is there any mathematical way for me to search this grid for patterns more efficiently than the naked eye? I can see that the vertical and horizontal lines are most prominent along the prime numbers, which is interesting.

Thank you, and sorry if this is a dumb question. I couldn't think of any other place to ask it.

share|improve this question

migrated from mathoverflow.net Sep 10 '13 at 0:18

This question came from our site for professional mathematicians.

    
This is known as Euclid's orchard. –  Rahul Apr 24 at 17:09

2 Answers 2

This pattern is usually described in the following way: Suppose you stand at the origin, and at each lattice point $(x,y)\in\mathbb{Z}^2$ there is a thin pole stuck into the ground. Which lattice points are visible, i.e. which poles are not hidden behind other poles? The answer is that $(x,y)$ is visible if and only if $x$ and $y$ have no common factor $>1$, since if $d$ is a common factor, then $(x,y)$ is hidden by $(x/d, y/d)$.

If you search for visible lattice points, you will find articles ranging from introduction to research papers.

share|improve this answer

This is a grid of coprimes. Coprimes are two numbers that don't share a common factor (Besides 1) Ex. 6 and 5 are, but 6 and 12 are not because 12 and six both share a common factor of 6. So this grid is essentially a IsComprime(x,y) function. That is why all the black vertical lines and horizontal lines are found on prime numbers, because there are no common factors. Coprime numbers have been researched, and this grid has been made before. The randomness is coming from the distribution of prime numbers, which is not entirely random, be it appears to be. This also related to the sieve of Eratosthenes because for each grid you are cancelling out a portion of values spaced with in the code :
while((xt < width && yt < height) && (xt != 0 || yt != 0)) { grid[xt][yt] = false;

              xt += x;
              yt += y;
          }
share|improve this answer
    
One additional note related to this characterization: it can be proved that the grid has a density of $\frac{6}{\pi^2}$, in the sense that if you take an $N\times N$ square with one corner at the origin, then the number of 'on' cells in that square tends towards $\frac{6}{\pi^2}N^2$ as $N\to\infty$; see en.wikipedia.org/wiki/Coprime_integers#Probabilities for some details on this. –  Steven Stadnicki Apr 24 at 17:04

Your Answer

 
discard

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