The Prime Tableau and the Rational Primitive Mask

The Procedure

October 2013

The following tabular procedure generates the rational primitive mask, that is, an infinite grid of binary values (a bitmap) showing the locations of all the primitive rational numbers i/j (a "primitive rational" is what was called a "reduced fraction" in elementary school). A side effect of this process is that it also graphically identifies and enumerates the values of the prime numbers, by a simple binary sequence pattern. Hence the name "Prime Tableau". The process of generating the mask involves only the copying of binary sequences, starting from an initial sequence of 3 numbers, in order to build the Tableau to any size. This process only generates 1/8 of the mask, in an infinite triangular area, but the other 7 parts of the grid are identical by symmetry. There are two slightly different procedures, called the "column" and "row" methods respectively, based on how the Tableau is built, but the result is the same. The column method is the slightly simpler of the two.

The column method

The following steps can be performed with paper and pencil, in which case quad-ruled paper might be easier, or in a text editor on a computer, etc... Some C and Javascript code you can use are provided on other pages of this site. This method is best if you want to build a complete Tableau (some number of lines) in one go. The row method is used to build a Tableau incrementally one line at a time. See the test page for an example of the row method implemented in C.

1. Write down the 3 numbers 1, 1, 0 vertically at the top left corner in the first column like this:
2. 3. Below the 0, add more rows of 0's in the first column for as long as you need (they go on infinitely down the page):
4. 5. To create the second column, first note that there is a 1 in the second row of the first column. Write that symbol (a 1) next to it in the second column of the second row:
6. 7. Repeat that sequence (currently just a 1) down the second column, for as long as you need:
8. 9. To create the third column, note that there is the sequence '0 1' in the third row. Write that sequence vertically next to it starting in the third column of the third row (the 0) and down into the third column of the fourth row (the 1):
10. 11. Repeat that sequence (now '0 1') down the third column, for as long as you need:
12. 13. For all the other columns you need, repeat steps 3 and 4: (3) in the next row, identify the sequence of symbols in the row and copy them vertically alongside to start the next column, and then (4) repeat that sequence down the column:
14. 15. As you complete the rows of the Tableau, note that starting with the third row there are some row sequences that consist of an initial 0, an unbroken block of 1's, and a final 0. These sequences indicate the prime numbers. The prime value is both the index of the row (starting with 0 at the top) and the number of 1's in the row sequence, plus 1. More specifically, a row indicates a prime if, between the first and last symbol on the row (there must be at least 2) there are no 0's. This definition also includes the number 1:
16. Et voilà! That's it!

(Note: Actually, while the solid block of 1's between the first column and diagonal is visually easy to identify, a prime row needs only to have a 1 in every column corresponding to a previous prime row. So, for example, to detect 11 as prime it is only necessary to check for a 1 in columns 1, 2, 3, 5, and 7. A further refinement can be made by only checking the prime columns less than or equal to the square root, so that in the case of 11, only columns 1, 2, and 3 need to be checked.)