Could these be called prime vectors?

Question

Some time ago I asked the following question: in polar coordinates, what is the first vector I can find with integer components? As I could not find the answer easily, I wrote a program to generate those vectors. It works like this:

1 - I define this data structure:

struct Point {
  int order;
  double r;
  double theta, phi;
};

2 - A bidimensional array of such structures (n x n) is created and all array elements are marked with .order = 0;

3 - The array is populated like an onion, in layers that start from the origin:

  long nI, nJ, nLayer, nIndex;

  for (nLayer=1; nLayer < SIZE; nLayer++) {
    std::cout << std::endl << "Calculating layer " << nLayer << std::endl;

    for (nI = 0; nI <= nLayer; nI++) {
      nJ = nLayer;
      nIndex = GetIndex(nI, nJ);

      if (m_asPrimaryCoordinates[nIndex].order == 0) {
        m_asPrimaryCoordinates[nIndex].order = 1;
        MarkHigherOrderCoordinates(nI, nJ);
        std::cout << "(" << nI << "," << nJ << ") ";
      }
    }

    for (nJ = 0; nJ <= nLayer; nJ++) {
      nI = nLayer;
      nIndex = GetIndex(nI, nJ);

      if (m_asPrimaryCoordinates[nIndex].order == 0) {
        m_asPrimaryCoordinates[nIndex].order = 1;
        MarkHigherOrderCoordinates(nI, nJ);
        std::cout << "(" << nI << "," << nJ << ") ";
      }
    }

For each element i,j of the array:

• if the .order property of that element equals zero, it is set to one. That element represents a vector with integer components which is not the product of an integer scalar (except one) by another vector with integer components.

• in case the element was marked as one, all array elements that lie within array bounds, and are products of this vector by an integer scalar, are marked with .order equals that scalar. For example, element (1,1) has .order equal one, so 2*(1,1) has its .order property marked as 2, 3*(1,1) has its .order property marked as 3 etc.

• if the .order property of the element is different from zero, it is not changed.

After populating all the array following this procedure, elements with order one are plotted and we see the following pattern:

Pattern generated. Marked points are vectors with integer coordinates that are not the product of another vector with integer coordinates by an integer scalar.

The picture shows that:

1. Elements with .order 1 form a clear pattern of cells with walls.

2. There is an empty diagonal on the pattern, formed by vectors which are the product of (1,1) by an integer scalar;

3. Elements that constitute cell walls have common coordinates (e.g. (5,1),(5,2),(5,3),(5,4)) that follow this rule:

Formula1

where n is an integer and

Formula2

and

Formula3

4. Common coordinates of cell wall elements can be prime. Elements that do not constitute cell walls cannot have prime coordinates. Searching for prime numbers seems to be an easier task now.

5. When a cell wall is not interrupted between x=0 (or y=0) and the diagonal, the wall elements' common coordinate is a prime number.

6. Interruptions on cell wall continuity are caused by cell wall elements multiplied by an integer scalar which is prime, i.e., by another cell wall vector of higher .order.

Based on the discoveries above, I ask the following questions:

1. Can the array elements with .order equal one be called prime vectors?
2. Is there a way to predict when the w(n) rule will generate a non prime number?

Answer 1

What you've invented is actually the concept of coprimality. A vector $(a,b)$ will have "order one" in your notation iff $\gcd(a,b)=1$, for if $\gcd(a,b)=k>1$, then we can divide by $k$: $(a,b) = k \cdot \left(\frac{a}{k},\frac{b}{k}\right)$, thus $(a,b)$ will have order $k$.

Long lines of "walls" are generated by prime coordinates: for $p$ prime, you'll have a vertical line of type $(p, y)$, with the only exception being the case $y = kp$ (which happens rarely for large $p$). Intersection of several lines of prime type produce "cells".

The cells are often very close to each other, separated by an almost empty strip of width 1. This is related to twin primes - there are many of them.

Numbers like $6$ or $30$ have many small prime divisors, thus they are rarely coprime to others. This is clearly seen on your image: corresponding rows & columns are almost empty.

It is hard to tell which exact pattern you are talking about. I'll assume that the lines with numbers $1,5,7,11,13,17,19,23,25,29,31,35,37,\dots$ are of your interest. They are related to number $6$.

$6$ is interesting because every number is it is the first to possess two prime factors: $6=2\cdot 3$, and this prime numbers are the two smallest ones. $6$ is rarely coprime to others - the probability is $\frac{1}{3}$, since among the $6$ possible remainders after dividing by $6$, which are $0,1,2,3,4,5$, only two mean that a number is coprime to $6$, namely $1$ and $5$. So, the remainder after dividing by $6$ is a simple yet effective primality test (which can - and will - yield false positive results).

Look closer to the sequence above: these are precisely the numbers that leave a remainder of $1$ or $5$ after being divided by $6$. So, this numbers are coprime to $6$, thus may be prime and may produce long walls. Indeed, most of the numbers in this sequence are prime, but not all of them - notice the $35$, which is $5\cdot 7$, and has lots of cracks in its walls.