			PRIME NUMBERS for the hp-48

			BY Francisco RAMOS HERMAN
				fbramos@teleline.es




The program for prime number calculation included in the 
directory 'PRIME' is 'ZIEB'. It works with an improved 
sieve of Erastothenes algorithm.

'ZIEB' calculates all prime numbers from 2 to the number in the X stack.

-> 50 'ZIEB' returns { 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 }

It would greatly increase in speed if any of you could program it
in machine language for the hp-48 series.Please contact me if you
are interested in doing so.It uses the subroutines 'NN','NMP' and 'CLR'.


I use the fact than all primes greater than 3 are of the form 6*n-+1
with n natural.(Wich I call the 'Gueto theorem' in honor to a good 
friend of mine. It is really easy to prove.)

The two lists one gets are:

   n      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37             

(6*n-1)-> 5 11 17 23 29 35 41 47 53 59 65 71 77 83 89 95 101 107 113 119 125 131 137 143 149 155 161 167 173 179 185 191 197 203 209 215 221...

(6*n+1)-> 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 96 103 108 115 121 126 133 139 145 151 157 163 169 175 181 187 193 199 205 211 217 223...             


All primes greater than 3 are in these two lists.


Now one must "clean" them of all non primes.



The non primes in the 6*n-1 list are:  35   65    77    95   119   125    143   155   161   185   203  209   215    221 ...
                                      5*7  5*13  7*11  5*19  7*17  5*25  11*13  5*31  7*23  5*37 7*29 11*19 5*43  13*17
                (6*n-1) with n =       6    11    13    16    20    21     24    26    27    31   34    35   36     37


They are products of   (6*n-1) and (6*(n+i)+1)   like 5*7 5*13 5*19 5*25 11*13...
with 
    n=1,2,3...
    i=0,1,2,3...

        or products of (6*n+1) and (6*(n+i)-1)   like 7*11 7*17 7*23 7*29 13*17...
with 
   n=1,2,3...
   i=1,2,3....


We get two "metaseries" of numbers to be cleaned out the (6*n-1) list.

First series:

(6*n-1)(6*n+1) = 6*m-1  -> m = 6*n^2   with n=1,2,3...

This gives for m the series  m =  6 ,  24   ,  54...
                                 5*7  11*13   17*19

Second series:

(6*n+1)(6*(n+1)-1) = 6*m-1 -> m = 6*n^2 + 6*n +1  with n=1,2,3...


This gives for the m series m =  13   ,   37   ,    73...
                                7*11    13*17     19*23




Now look at what happens if we put these two series together and order them.

For n = 1,2,3...

we get m= {6 13 24 37 54 73...}

All this numbers are in the non prime list for (6*n-1)!


And now let's do some prime number magic.

We take each of these "seeds" one by one and add to it in sequence the 
(6*n-+1) number than corresponds to it.

    +5   +5   +5   +5
6   11   16   21   26...

    +7   +7   +7   +7
13  20   27   34   41...

   +11   +11  +11  +11
24  35    46   57   68...

   +13  +13  +13  +13
37  50   63   76   89...

   +17  +17  +17  +17
54  71   88  105  122... 

   +19  +19  +19  +19
73  92  111  130  149...

If we order the numbers we have obtained we get the following list:

{6 11 13 16 20 21 24 26 27 31 34 35 36 37 41 46 48 50 51 54 55 56 57 61...}

We get all the non prime numbers to be removed from the 6*n-1 series!!!



We now proceed to the non primes in the 6*n+1 list.


The non primes in the 6*n+1 list are:  25  49  55   85   91  115   121  133  145   169  175   187  205   217...
                                      5*5 7*7 5*11 5*17 7*13 5*23 11*11 7*19 5*29 13*13 5*35 11*17 5*41 7*31
                 (6*n+1) with n =      4   8   9    14   15   19    20   22   24    28   29    31   34   36


They are products of (6*n-1) and (6*(n+i)-1) like 5*5 5*11 5*17 5*23 11*11 5*29 5*35 11*17 5*41...
with 
     n = 1,2,3...
     i = 0,1,2,3...
      
      or products of (6*n+1) and ( 6*(n+i)+1) like 7*7 7*13 7*19 13*13 7*31...
with 
    n = 1,2,3... 
    i = 0,1,2,3...

We get two "metaseries" of numbers to be cleaned out the (6*n+1) list.

First series:

(6*n-1)(6*n-1) = 6*m+1  -> m = 6*n^2 + 2*n   with n=1,2,3...

This gives for m the series  m =  4 ,  20   ,  48...
                                 5*5  11*11   17*17

Second series:

(6*n+1)(6*n+1) = 6*m+1 -> m = 6*n^2 - 2*n   with n=1,2,3...


This gives for the m series m =  8   ,   28   ,    60...
                                7*7    13*13     19*19


Now look at what happens if we put these two series together and order them.

For n = 1,2,3...

we get m= {4 8 20 28 48 60...}

All this numbers are in the non prime list for (6*n+1)!


And now let's do some more prime number magic.

We take each of these "seeds" one by one and add to it in sequence the 
(6*n-+1) number than corresponds to it.

    +5   +5   +5   +5
4    9   14   19   24...

    +7   +7   +7   +7
8   15   22   29   36...

   +11   +11  +11  +11
20  31    42   43   54...

   +13  +13  +13  +13
28  41   54   67   80...

   +17  +17  +17  +17
48  65   82   99  116... 

   +19  +19  +19  +19
60  79   98  117  136...

If we order the numbers we have obtained we get the following list:

{ 4 8 9 14 15 19 20 22 24 28 29 31 34 36 39 41 42 43 44 48 49 50 53 54...}

We get all the non prime numbers to be removed from the 6*n+1 series!!!

Thats it!

We now have two lists with only prime numbers in them!

In someway this could mean than the prime numbers have a structure!

And I have found it out!

It could be called a recurrent structure.
For they all are found out with a double recursion.

As one said: "Iteration is human, recursion is divine"

(Sorry I do not remember who said that.)

I am working on two more things who derive from this work:

First:  A program to calculate prime numbers in a given range using
these algorithms.I have a working one allready but it still has some bugs.
If you are interested anyway or would like to help finding out the bugs
please contact me!


Second : It has not yet been proved than the number of "twin-primes"
is infinite ( it means pairs of primes separated by 2 
like 5,7 11,13 191,193...). My intuition tells me they are infinite
from what I have discovered working with the 6*n-+1 series.
If you are into number theory and are interested to work on this proof
and want my help or to help me please contact me!




Now some notes on the program:

'ZIEB' generates two  constant matrixes for the 6*n-1 and 6*n+1 series. 
They are full of ones to be changed by 0 for the non prime numbers.

The subroutine 'NN' calculates all "seeds" for the 6*n+1 series up to a given
n.

The subroutine 'NMP' calculates all the "seeds" for the 6*n-1 series up to 
a given n.

The subroutine 'CLR' is used to clear all non prime numbers from the matrixes
given the calculated "seeds".


Included are two programs ('C' and 'CM') who work after the normal 
sieve of Erastothenes algorithm. You can this way compare times of execution 
using the program 'deltaTIME'.

'C' and 'CM' calculate a list of primes up to a given number in the x stack.
'C' displays the prime numbers as they are found out.

'deltaTIME' is useful to find out execution times of programs in seconds.
Enter the needed input(s) for a given program and then the name of the 
program. Then press 'deltaTIME' you will get the results of the program
and the execution time in seconds.
It is useful to improve programs speeds.

For example for 100 'CM' 'deltaTIME' 
I get the prime numbers from 2 to 100 in 6.92 seconds on my hp-48gx

for 100 'ZIEB' 'deltaTIME'
I get the prime numbers from 2 to 100 in 2.85 seconds wich is faster!


And as prime number calculation times grow up exponentially you can guess
how much time you spare!

And wait until this program works in machine language!


Also included is a list of prime numbers from 1 to 10 000 calculated using
this program. It is in the 'DATA' directory.


That's it for today.

I hope you enjoyed the ride!

Francisco RAMOS HERMAN



P.S.: one more thing: If you work for Hewlett and Packard and are interested
in this program to include it in some math package for any HP calculator
feel free to contact me.
I think the program to calculate prime numbers in a certain range will be far
more interesting. I am working o it.













