The Prime Tableau and the Rational Primitive Mask

Test

October 2013

In order to test the Tableau procedure, first 2 published tables of prime numbers were downloaded and converted to a single column of text:

1. http://www.math.utah.edu/~pa/math/p10000.html
2. http://primes.utm.edu/lists/small/10000.txt

These two lists are identical.

Next, the C program shown on a previous page was modified to output just the prime numbers it finds, rather than the entire Tableau.

```// list_primes.c
// converted from bootstrap_pm.c
// generate prime tableau by column method
// output only list of primes
// 10/5/13

// compile with: cc -O3 -o list_primes list_primes.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
if (argc < 2)
{
printf("Usage: list_primes nlines\n");
return 1;
}
int nlines = strtol(argv[1], 0, 10);

int nx = nlines, ny = nlines;
char *pm = (char *) malloc(nx * ny); // rational primitive mask
int i, j;
for (i = 0; i < nx * ny; i ++) pm[i] = -1;

unsigned char *isPrime = (unsigned char *) malloc(ny); // prime mask
isPrime[0] = 0; // 0 is not prime

// the "column" method: first column
pm[0] = 1;
pm[nx] = 1;
for (j = 2; j < ny; j ++)
pm[nx * j] = 0;

// all other columns
for (i = 1; i < nx; i ++)
{
int k = 0; // index into ith row sequence
for (j = i; j < ny; j ++)
{
// set value in column to value in row sequence
pm[i + j * nx] = pm[k + i * nx];
// increment index and possibly wrap
k ++;
if (k >= i) k = 0;
}
}

// detect primes
for (j = 1; j < ny; j ++)
{
int ok = 1;
// pm must be all 1s between (not including) first column and diagonal
for (i = 1; i < j; i ++)
if (pm[i + j * nx] == 0)
{
ok = 0;
break;
}
isPrime[j] = ok;
}

// print (skipping 1 for compatibility with other lists)
for (j = 2; j < ny; j ++)
if (isPrime[j]) printf("%d\n", j);

return 0;
}
```

This program was then used to create a Tableau with 40000 lines (about the biggest I could do with a single block malloc call) and output only the primes (omitting 1 for compatibility). This produced output of 4203 primes, from 2 to 39989, which was then compared to the 2 published lists, and is found to be identical up through the first 4203 lines. The file 'primes3_list.txt' shown below was created by the Tableau program.

In order to test the time/space properties of the Tableau, and to illustrate the row method of Tableau construction, a new program was created that builds the Tableau row-by-row rather than column-by-column. This program also allocates individual arrays for each row of the table to avoid memory waste and multiplication to find element offsets. To also avoid modulo math, indices for each row sequence are maintained, which makes the logic slightly more complicated than the column method. This code is also available as a file for download.

```// pt_by_rows.c
// generate prime tableau row-by-row rather than column-by-column
// gather statistics on run time and memory usage wrt tableau size
// 10/5/13

// compile with: cc -O3 -o pt_by_rows pt_by_rows.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

// vars to hold time
struct timeval tv;
double t0 = 0.0;

// data
unsigned long allocated = 0;
unsigned char **rows;
int printData = 1;

// get elapsed time
double elapsedTime()
{
gettimeofday(&tv, 0);
double t = tv.tv_sec + tv.tv_usec * 1.0e-6;
return t - t0;
}

// detect primes
int isPrime(int j)
{
if (j < 1) return 0; // 0 is not prime
int i;
// row must be all 1s between (not including) first column and diagonal
for (i = 1; i < j; i ++)
if (rows[j][i] == 0) return 0;
return 1;
}

// print row plus time and space
void printRow(int j)
{
printf("%7d  %10.3f %12lu", j + 1, elapsedTime(), allocated);
int is_prime = isPrime(j);
if (is_prime) printf("  %7d", j);
if (printData)
{
if (is_prime) printf(" - ");
else printf("            ");
int i;
for (i = 0; i <= j; i ++)
printf("%1d", rows[j][i]);
}
printf("\n");
}

int main(int argc, char *argv[])
{
if (argc < 2)
{
printf("Usage: pt_by_rows nlines {0 to suppress row data}\n");
return 1;
}
int nlines = strtol(argv[1], 0, 10);
if (argc > 2) printData = strtol(argv[2], 0, 10);

// initialize time
gettimeofday(&tv, 0);
t0 = tv.tv_sec + tv.tv_usec * 1.0e-6;
//printf("t0 = %.3f\n", t0);

// initial allocation
int nx = nlines, ny = nlines;
rows = (unsigned char **) malloc(ny * sizeof(unsigned char *));
allocated += ny * sizeof(unsigned char *);
int *rowIndices = (int *) malloc(ny * sizeof(int));
allocated += ny * sizeof(int);

// create and print first two rows
int i, j;
rows[0] = (unsigned char *) malloc(1);
allocated += 1;
rows[0][0] = 1;
printRow(0);

rows[1] = (unsigned char *) malloc(2);
allocated += 2;
rows[1][0] = 1;
rows[1][1] = 1;
rowIndices[1] = 0;
printRow(1);

// create and print additional rows
for (j = 2; j < ny; j ++)
{
// allocate and initialize row
rows[j] = (unsigned char *) malloc(j + 1);
allocated += j + 1;
// set first column and diagonal
rows[j][0] = 0;
rows[j][j] = 0;
rowIndices[j] = 0;

// set other columns from previous row sequences
for (i = 1; i < j; i ++)
{
// increment and possibly wrap row sequence index
rowIndices[i] ++;
if (rowIndices[i] >= i) rowIndices[i] = 0;
// set element
rows[j][i] = rows[i][rowIndices[i]];
}

// print
printRow(j);
}

return 0;
}
```

This program can be used to generate and output the Tableau row data, or just the elapsed time, memory use, and primes.

```2: ~/Sites/Tableau/Code/C > cc -O3 -o pt_by_rows pt_by_rows.c
3: ~/Sites/Tableau/Code/C > pt_by_rows
Usage: pt_by_rows nlines {0 to suppress row data}
4: ~/Sites/Tableau/Code/C > pt_by_rows 33
1       0.000          397            1
2       0.000          399        1 - 11
3       0.000          402        2 - 010
4       0.000          406        3 - 0110
5       0.000          411            01010
6       0.000          417        5 - 011110
7       0.000          424            0100010
8       0.000          432        7 - 01111110
9       0.000          441            010101010
10       0.000          451            0110110110
11       0.000          462            01010001010
12       0.000          474       11 - 011111111110
13       0.000          487            0100010100010
14       0.000          501       13 - 01111111111110
15       0.000          516            010101000101010
16       0.000          532            0110100110010110
17       0.000          549            01010101010101010
18       0.000          567       17 - 011111111111111110
19       0.000          586            0100010100010100010
20       0.000          606       19 - 01111111111111111110
21       0.000          627            010100010101010001010
22       0.000          649            0110110010110100110110
23       0.000          672            01010101010001010101010
24       0.000          696       23 - 011111111111111111111110
25       0.000          721            0100010100010100010100010
26       0.000          747            01111011110111101111011110
27       0.000          774            010101010101000101010101010
28       0.000          802            0110110110110110110110110110
29       0.000          831            01010100010101010101000101010
30       0.000          861       29 - 011111111111111111111111111110
31       0.000          892            0100000100010100010100010000010
32       0.000          924       31 - 01111111111111111111111111111110
33       0.000          957            010101010101010101010101010101010
5: ~/Sites/Tableau/Code/C > pt_by_rows 33 0
1       0.000          397
2       0.000          399        1
3       0.000          402        2
4       0.000          406        3
5       0.000          411
6       0.000          417        5
7       0.000          424
8       0.000          432        7
9       0.000          441
10       0.000          451
11       0.000          462
12       0.000          474       11
13       0.000          487
14       0.000          501       13
15       0.000          516
16       0.000          532
17       0.000          549
18       0.000          567       17
19       0.000          586
20       0.000          606       19
21       0.000          627
22       0.000          649
23       0.000          672
24       0.000          696       23
25       0.000          721
26       0.000          747
27       0.000          774
28       0.000          802
29       0.000          831
30       0.000          861       29
31       0.000          892
32       0.000          924       31
33       0.000          957
```

I have run this program, minus row output, for 100000 lines in order to see the elapsed time and memory usage. The run took 2 min 10 sec and used 4.66 GB on my MacBook Pro 2 GHz Intel Core i7. The following is an excerpt of the output. (12/14/14: This run takes 1 min 29 sec on my i5-4590 3.3 GHz running Linux.)

```      1       0.000      1200001
2       0.000      1200003        1
3       0.000      1200006        2
4       0.000      1200010        3
5       0.000      1200015
6       0.000      1200021        5
7       0.000      1200028
8       0.000      1200036        7
9       0.000      1200045
10       0.000      1200055
...
99989     130.172   5000150055
99990     130.176   5000250045    99989
99991     130.179   5000350036
99992     130.183   5000450028    99991
99993     130.186   5000550021
99994     130.190   5000650015
99995     130.193   5000750010
99996     130.197   5000850006
99997     130.200   5000950003
99998     130.204   5001050001
99999     130.207   5001150000
100000     130.210   5001250000
```

Plots of time and space are shown below.

If you would like to make your own plots, the data file is here.