The Prime Tableau and the Rational Primitive Mask

Background

October 2013

I wanted to do some programming work on the fractions (yes, the "fractions" that everyone found dull in elementary school) that wouldn't just be goofy characters dancing across the screen, etc..., but would be something more "serious" and potentially useful, or at least interesting to me. So I started by displaying the fractions, formally known as the "rational numbers" (which are all values i/j for integers i and j), as a 2d grid of cells where the horizontal coordinate i was the numerator and the vertical coordinate j was the denominator. I include 0 as a value for i and j so that 0/j = 0, i/0 = Infinity, and 0/0 = Anything (see below for explanation):


The rationals can be divided into equivalence classes where numerator1 * denominator2 = numerator2 * denominator1. In the image above, the equivalence class {0/0, 1/1, 2/2, 3/3, ...} is shown along the diagonal, because 1 * 2 = 2 * 1 and 1 * 3 = 3 * 1 and 2 * 3 = 3 * 2, etc... Similarly, 0/1 is equivalent to 0/0, 0/2, 0/3, etc..., with all in the first column of the grid. And 1/0 is equivalent to 0/0, 2/0, 3/0, etc..., with all in the first row of the grid. And 0/0 is equivalent to everything, because 0 * j = i * 0 for any i and j:


In general, any rational number you choose will be equivalent to an infinite number of other rationals all located on a ray originating at 0/0 and having a angle with respect to the j axis (denominator) of from 0 to 90 degrees. Each equivalent rational will be spaced evenly along this ray. For each such class, there is a rational other than 0/0 that is closest to the origin. For example, for the rational 3/6, the closest equivalent rational is 1/2. This closest rational I call the "quantum" of the set, as it defines the angle of the ray and the distance between rationals spaced along it. This quantum is also called the "reduced fraction", but I prefer my terminology. All rationals along the ray are multiples of this quantum in both numerator and denominator. If a rational is equal to its quantum, that is, it is the closest to the origin along its ray, then I say that rational is "primitive" to distinguish it from its multiples. So, for example, 6/4 is not primitive, but 3/2 is.


If we zoom out the grid and begin selecting different points, we see that some of them are multiples of points closer to the origin, and that some of them are the closest points themselves: they are primitive rationals. After doing this a while, it is natural to wonder if there is any structure to this distribution. That is, which of these points are primitive, where are they located (e.g. closer to the origin?), and how many of them are there, compared to the rest of the rationals?


We can make plots of these points by calculating, for every rational i/j in a part of the grid, whether it is primitive of not. This is done by calculating the quantum of every point and seeing whether it is equal to the point itself. How each quantum is calculated is not important here, except to say that is does take a bit of time to do for every i/j in the 2d grid. Usually, fractions are reduced by factoring, but I am using another method here. The following is a plot of all rationals for i and j from 0 to 750. The color is the distance of the point from the origin, from blue to red. Only those points that are primitive are shown. All non-primitive rationals are black. If we interpret this plot as binary values, where there is a 1 for every primitive rational and a 0 for all others, then it becomes what I call the "rational primitive mask", and goes on infinitely in both i and j (actually, if i and j are allowed to be negative, the grid goes on infinitely in all directions). This mask is important to the work I am currently doing, as most of my investigations (e.g. repeating sequence lengths of long division) concern only the primitive rationals.


Below is a close-up of the primitive mask near the origin. We can immediately note some features. First, it is symmetric about the diagonal, which makes sense from our definitions of rational equivalence classes along rays and the quantum of each. Starting with 2/2 onward, none of the points on the diagonal are primitive, so the black line goes on forever. Similarly, starting with 0/2 onward and with 2/0 onward, none of the points in the first row or column are primitive. But what about the rest of the mask? Certainly the structure looks interesting, but it doesn't look regular.


Next is a close-up of another part of the grid, still along the diagonal, but now starting at i = j = 10000. All of the colors are similar because all of the points are at about the same distance from the origin, and far from it. (As you might expect, performing calculations with rationals far from the origin takes much more time to do.)


Next is a close-up of another, random, part of the grid (starting at 3324, 7176) far from the diagonal. Again we see a similar, but subtly different, structure. In all cases I have tried (albeit still "close" to the origin in an infinite grid!) I have seen similar results.


We can summarize 3 important features of these results in the following:

  1. The primitive rationals appear to be distributed uniformly across the infinite grid, rather than being clumped near to the origin or elsewhere.

  2. There is a fine structure to the distribution of primitives which appears to be similar in every subset of the grid.

  3. If we perform multiple samples of the grid, at different random locations, and count the number of primitives within each sample, we see that on average about 60.8% of all rational numbers are primitive. Sometimes a little more, sometimes a little less, but not by much.

These results are somewhat surprising (at least to me!), especially the third one. Below is a log of sampling the grid in 750x750 point chunks out to 10000, 10000, counting the number of primitives in each sample, and keeping a running total of the percentage.

at 5070, 6888: 341829 of 562500 are primitive (60.77 %)
   n = 1, mean = 60.770, std = nan
at 1677, 2662: 341961 of 562500 are primitive (60.79 %)
   n = 2, mean = 60.781, std = 0.000275
at 608, 1326: 341806 of 562500 are primitive (60.77 %)
   n = 3, mean = 60.776, std = 0.000221
at 1958, 9187: 342000 of 562500 are primitive (60.80 %)
   n = 4, mean = 60.782, std = 0.000291
at 5105, 3468: 341919 of 562500 are primitive (60.79 %)
   n = 5, mean = 60.783, std = 0.000221
at 8832, 5940: 341868 of 562500 are primitive (60.78 %)
   n = 6, mean = 60.782, std = 0.000183
at 649, 8346: 341834 of 562500 are primitive (60.77 %)
   n = 7, mean = 60.780, std = 0.000170
at 302, 1372: 342022 of 562500 are primitive (60.80 %)
   n = 8, mean = 60.783, std = 0.000217
at 3913, 497: 341879 of 562500 are primitive (60.78 %)
   n = 9, mean = 60.783, std = 0.000192
at 9437, 8172: 341856 of 562500 are primitive (60.77 %)
   n = 10, mean = 60.782, std = 0.000177
...
at 1931, 1566: 342065 of 562500 are primitive (60.81 %)
   n = 25, mean = 60.787, std = 0.000256

Smaller sample sizes (100x100) produce more variation, but essentially the same result.

at 3771, 3062: 6056 of 10000 are primitive (60.56 %)
   n = 1, mean = 60.560, std = nan
at 8902, 3191: 6099 of 10000 are primitive (60.99 %)
   n = 2, mean = 60.775, std = 0.092450
at 6626, 4816: 6084 of 10000 are primitive (60.84 %)
   n = 3, mean = 60.797, std = 0.047633
at 5207, 2624: 6083 of 10000 are primitive (60.83 %)
   n = 4, mean = 60.805, std = 0.032033
at 4445, 5793: 6065 of 10000 are primitive (60.65 %)
   n = 5, mean = 60.774, std = 0.028830
at 2608, 5454: 6088 of 10000 are primitive (60.88 %)
   n = 6, mean = 60.792, std = 0.024937
at 1471, 3536: 6089 of 10000 are primitive (60.89 %)
   n = 7, mean = 60.806, std = 0.022162
at 5326, 8439: 6065 of 10000 are primitive (60.65 %)
   n = 8, mean = 60.786, std = 0.022027
at 4514, 3635: 6100 of 10000 are primitive (61.00 %)
   n = 9, mean = 60.810, std = 0.024350
at 6056, 6241: 6086 of 10000 are primitive (60.86 %)
   n = 10, mean = 60.815, std = 0.021894
...
at 8082, 2257: 6073 of 10000 are primitive (60.73 %)
   n = 100, mean = 60.772, std = 0.037835

Of course many of you will recognize the value 0.608 as being very close to 1 / φ = φ - 1, where φ is the golden ratio of about 1.6180339887... I have wondered whether it is the case (and some other people have also suggested) that as the samples of the grid go further and further from the origin they also asymptotically approach 1 / φ. I have not performed experiments to see if this is indeed true (this seems like a job for someone with a super-computer) but even if it is, one would need to explain why this is so. Please let me know if you have any ideas!

Here my work with the rationals goes off in another direction, so I'll move on to the prime numbers and the Tableau for generating them. As we do that, keep in mind the question of what the structure of the rational primitive mask might be, and is there a way to calculate it other than finding the quantum of every individual point in the grid independently of all others? The answer to this question is a resounding "yes", and the procedure for doing so is incredibly simple and involves very little math.

To figure out this pattern, let's look again at the primitive mask near the origin. This time I've added the indices for i and j, and color-coded some of these numbers (the primes).


To make a long story shorter, I'll just tell you some of my observations about this plot:

  1. The mask is symmetrical about the diagonal. I mentioned this before, but it is essential. This means that every jth row is identical to the jth column as well.

  2. Every row (or column) begins with a unique finite-size pattern. If we let 0 mean a black (non-primitive) square, and 1 mean a colored (primitive) square, then these patterns can be written as sequences of 0's and 1's.

  3. Each sequence of 0's and 1's for each row (or column) starts in the first column (row) and ends in the square just before the diagonal. Starting with the diagonal, each pattern then repeats itself over and over again, forever. Thus, the sequence in row 1 (column 1) is just '1' (that is, it starts with a 1 and then repeats itself beginning at the diagonal, creating a solid row of 1's). The sequence in row 2 is '0 1', and the sequence in row 3 is '0 1 1', etc...

  4. I have highlighted the prime numbers in yellow. In the case of a prime number row or column, the sequence is always (starting with row 2) a 0 followed by a contiguous block of 1's, such that for a prime number n, the sequence is a 0 followed by n - 1 1's.

  5. Items 1-3 imply that the pattern in every row, up to the diagonal, is also repeated down the column from the diagonal, below the row. This fact gives us the procedure for creating the entire mask, given a small initial starting set.

Although the overall 2d pattern of the mask appears variegated, the entire pattern for prime rows and columns is simple: all values are 1 except for a 0 every n squares, starting with the first square, the second being the diagonal. This unique pattern allows one to quickly and easily identify the prime numbers within the mask. Wherever there is an unbroken sequence of 1's between the first column and the diagonal, that row index (starting at 0) is a prime number. And the number of 1's between the first column and the diagonal also gives you the prime values (just add 1). Thus we (or at least I) say that the mask both identifies and enumerates the prime numbers, by their unique patterns and their lengths.

The procedure for generating the rational primitive mask, or that part out to the diagonal, and thereby identifying and enumerating the prime numbers, I have named the "Prime Tableau", and it is as follows:

  1. Begin by writing downward on paper (or in a computer program) the sequence of the first column (column 0): '1 1 0 0 0 0...'.

  2. Add the sequences for each additional column (starting with 1) by:

    1. Identify the initial row i sequence for the column i you wish to add.

    2. Starting at the diagonal of row i, copy that sequence vertically down to start the new column.

    3. Continue repeating that sequence down the column ad infinitum (or for as many rows of the Tableau as you need).

For a more detailed explanation and example of this procedure, please see the procedure page. There is also a slightly different procedure that creates the Tableau row by row, rather than column by column.



©Copyright Sky Coyote, 2013. -- Tableau home