# 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 (nx,ny) = 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 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

That graph can also be generated by superimposing several grids in which you color red in the x and y axis those squares that are multiples of all the numbers except for 1. That is, if you superimpose the grids 2 * 2, 3 * 3, 5 * 5 , 7 * 7, 11 * 11, etc. you get that pattern. The grids 4 * 4, 6 * 6, 8 * 8, 9 * 9, etc. can be ignored, because these numbers can be factored and coincide with the grids of 2 * 2, 3 * 3, etc. That is, they coincide with the grids formed by prime numbers. With this procedure you get the following pattern (the upper left corner is the square 0.0 in all the images): image 1

From this image you can see a very interesting pattern: if I remove the layers of squares 2 * 2, 3 * 3, 5 * 5, etc. (small grids), the following pattern is observed: image 2

So, in the following way, I deduced this, which may really be nothing, but I do find it interesting: image 3

The diagonals formed by the lines that were seen before coincide with the red squares. I have marked some but are more. In the image you can see the first ones that come out clearly, that form 45, 30, 22.5, 18, 15 and 12.8 degrees with respect to the horizontal above. This results from dividing 90 degrees between 2, 3, 4,5, 6 and 7, respectively. Note that the only squares that do not match (which I haven't colored because of that reason) are the seconds of each diagonal starting from the origin (top right corner).

And not only that, if I'm not mistaken, the bisectors between the diagonal lines also coincide with the red squares, and also is the second square of the new diagonals that do not match: image 4, image 5, and image 6

In image 4, bisecting formed by diagonals of 30 and 45 degrees, in image 5, bisecting formed by diagonals of 22.5 and 45 degrees, and in image 6, bisecting formed by diagonals of 18 and 45 degrees.

I think all this may be related to the prime numbers, and I hope this can be useful. If there is an error in the explanation or in the images, say it.

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
• Are you talking about the possible primes in base 10? No number that ends in 5 can possibly be prime. I'm sorry, I don't quite understand your comment. – lustig Apr 27 '17 at 17:09

I've also made this graph sometime in the early 90's and noticed the diagonals. I note that they are formed by the multiples of primes. The multiples of 1: rise/run = 1/1; multiples of 2: rise/run = 2/1; ... etc. (I graphed in the 1st quadrant.)

Rather than focusing on only the red dots, it's interesting to focus on the white solid lines as well. Primes occur at the intersection of solid lines (no divisors of lesser value other than 1). So assigning a color to those lines can be of interest, as can be focusing on the patterns inside those squares, and the on-off pattern of the next higher line and the squares being formed by those unique on-off patterned lines.

Primes are definitely deterministic in where they appear, but the exact nature of the determinism is unknown and may even be unknowable. (I have a feeling it's recursive.) I came up with an algorithm that can output all primes in order if you seed it with a given prime and the primes that come before it that are higher than it's square root (you can start it at a very low prime in the list of all primes), but it doesn't appear to be good for finding huge primes because the computing time becomes outrageous.

I have an idea that the task could potentially be simplified, but I'm one of those "amateur mathematicians" and uncertain of that particular statement. The other statements, I'm confident about.