Random binary array shows patterns around prime numbers

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:

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.

-

migrated from mathoverflow.netSep 10 '13 at 0:18

This question came from our site for professional mathematicians.

This is known as Euclid's orchard. – Rahul Apr 24 '14 at 17:09
This is a similar but different construction, it might interest you youtube.com/watch?v=iFuR97YcSLM – DanielV Mar 25 '15 at 11:01

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.

-

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;
}

-
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 '14 at 17:04

I found this same pattern in the mid 80's. It reads, line by line:

1-All nymbers in base 1 may be prime;

2-All numbers that end in 1 in base 2 may be prime;

3-All numbers that end in 1 and 2 in base 3 may be prime;

4-All numbers that end in 1 and 3 in base 4 may be prime;

etc...

Thus, the 10th line or 1010001010:

10-All numbers in base 10 that end in 1, 3, 7 and 9 may be prime. As if we didn't know it already(:) The negations are more forceful, no "may be" about them: in base 10 no number that ends in 2, 4, 6, 8, and 0 can be prime.

Therefore, there is NO "randomness" in that graph that is not prime.

-
(ouch! Missimg a "5" on next-to-last graph, last sentence, sorry.) – Ivan Moraes Mar 25 '15 at 10:44