PRMP - an algorithm for generating the primes using only “+1” and “=”

[CraigD]

With number-theory threads such as Prime numbers, Integers By Number Of Divisors, The Starburst Challenge, and Katabatak Math languishing at a snail/turtles pace, I thought I’d throw out a couple of my findings, one old, one recent, that might have bearing on these threads.

 

As anyone who’s done integer arithmetic without a calculator knows, not all of the elementary operations – addition, subtraction, multiplication, and division – are equal in their elementary-ness. Division is the least of them – it’s not even a closed operation on the set of integers, unless split into two operations, integer division and integer remainder, AKA the modulo operation. It’s also the hardest, computationally, requiring at least 2 of the others elementary operations.

 

With this and the prime number in mind, I asked myself, is it possible to generate the prime numbers using just 2 operations: addition and the “equality” true/false operator. Here’s what I found:

 

The Prime Remainder Method of generating the Primes (PRMP) - an algorithm for generating the primes using only “+1” and “=”:

Where:

p() is an array consisting of all the primes. e.g: p(1)=2, p(2)=3, p(3)=5, r(4)=7, etc.

r() is an array consisting of the modular remainder of a number divided by each prime. e.g: for the number 6, r(1)=0, r(2)=0, r(3)=1, r(4)=6 … r(greater than 4)=6

i is an integer used to reference p() and r(). e.g: i=1, i=2, etc.

FLAG is a true/false flag used to detect when no non-zero modular remainders have been found.

 

1) Initialize all elements of r() to 1. Since 1 modulo any prime is 1, only r(1) need be considered – all others are equal.

2) Initialize all elements of p() to “unknown”. We intend to generate them, so can’t know them in advance.

3)(beginning of outermost loop) Initialize FLAG to “nothing equality encountered”

4) Initialize array index i to 1

5) Increment (add 1 to) r(i)

6) Compare r(i) to p(i)

7) if r(i) = p(i), set r(i) to 0, and note in FLAG that “equality encountered”

8) if p(i) is “unknown”, proceed to step 9.

Otherwise, increment i and repeat steps 5-8.

9) If FLAG is “equality encountered”, repeat steps 3-8.

Otherwise, a prime has been found. Proceed to step 10.

10) set p(i) = r(i)

11) set r(i+1) = r(i)

12) set r(i) = 0

13) repeat steps 3-8.

 

Here is an example of the algorithm generating the first 6 primes:

After steps 1-2: p(1…)=unknown, r(1…)=1

After steps 3-8: r(1…)=2

After steps 9-13: p(1)=2, p(2…)=unknown, r(1)=0, r(2)=2

After steps 3-8): r(1)=1, r(2)=3

After steps 9-13: p(2)=3, p(4…)=unknown, r(2)=0, r(3)=3

After steps 3-8: r(1)=0, r(2)=1, r(3)=4

After steps 3-8: r(1)=1, r(2)=2, r(3)=5

After steps 9-13: p(3)=5, p(5…)=unknown, r(3)=0, r(4)=5

more compactly:

r()=0 0 1 6

r()=1 1 2 0 7

r()=0 2 3 1 8

r()=1 0 4 2 9

r()=0 1 0 3 10

r()=1 2 1 4 0 11

r()=0 0 2 5 1 12

r()=1 1 3 6 2 0 13

p()=2 3 5 7 11 13

 

Note that, even allowing for it’s minimal arithmetic this algorithm is not computationally more efficient than many existing prime number generators. As the number of known primes increases, the number of increment and compare operations increases, making it very slow for large primes. Also, it must generate and store all of the primes beginning with 2, making it practically useless for generating very large primes. It’s only virtue is that it uses only 2 very elementary arithmetic operations.

 

The Sieve of Aristophanes is another prime number generator that requires an array but does not require division. However, the Seive can’t be generalized into doing more than generating the primes. PRMP can be extended to do at least a couple more interesting things. In an important way, I think, the r() array contains more useful information than an algorithm using just a p() array. In a later post, I’ll show an extension of PRMP that can make use of this additional information.

 

Does anyone know of other addition and equality only prime number generators?

[Turtle]

___I like the algorithm so far; I'm still getting it straight in my head. Overall, we seem always faced with some trade off or another; go faster, & we need more storage space, or economize the storage space & we slow down. Very interesting work Craig.

[CraigD]

PRMPF - generating the prime factorizations of the integers without using division.

 

In addition to telling us which integers are prime numbers, PRMP provides some information about the prime factorizations of integers that are composite numbers.

 

Take a look at the p() arrays for 2 through 30:

0 2
1 0 3
0 1 4
1 2 0 5
0 0 1 6
1 1 2 0 7
0 2 3 1 8
1 0 4 2 9
0 1 0 3 10
1 2 1 4 0 11
0 0 2 5 1 12
1 1 3 6 2 0 13
0 2 4 0 3 1 14
1 0 0 1 4 2 15
0 1 1 2 5 3 16
1 2 2 3 6 4 0 17
0 0 3 4 7 5 1 18
1 1 4 5 8 6 2 0 19
0 2 0 6 9 7 3 1 20
1 0 1 0 10 8 4 2 21
0 1 2 1 0 9 5 3 22
1 2 3 2 1 10 6 4 0 23
0 0 4 3 2 11 7 5 1 24
1 1 0 4 3 12 8 6 2 25
0 2 1 5 4 0 9 7 3 26
1 0 2 6 5 1 10 8 4 27
0 1 3 0 6 2 11 9 5 28
1 2 4 1 7 3 12 10 6 0 29
0 0 0 2 8 4 13 11 7 1 30

The location of zeros tell us which primes are present in each number’s prime factorization.

For example, 12= 2^? * 3^?, while 30=2^? * 3^? *5^?.

 

The point of these algorithms has been, and continues to be, avoiding the “hard” operation of integer division. Determining the values of the “?”s above require repeated division, so something beyond the PRMP will be needed in order to generate not just the primes, but the prime factorization of every integer.

 

Consider this algorithm:

PRMPF - “+”,”=”, and ”*” only prime factor generator:

Where:

p() is a 2-dimensional array consisting of all the primes, raised to the non-negative integer powers. E.g: p(1,1)=2, p(1,2)=3, p(1,3)=5, p(2,1)=4, p(2,2)=9, p(2,3)=25, p(3,1)=8

r() is a 2-dimenstional array consisting of the modular remainders of a number divided by the corresponding p(,). E.g: for the number 6, r(1,1)=0, r(1,2)=0, r(1,3)=1, r(1,4…)=6, r(2,1)=2, r(2,2…)=6, r(3…,…)=6.

i, j are integers used to reference p() and r(), eg: p(i,j)

e() is a 1-dimensional array of the greatest values of j for which r(i,j)=0, which are the exponents of the prime factorization of the number. E.g: for the number 6, e(1)=1, e(2)=1

 

1) Initialize r(1,1)=1

2) clear all defined e(j)s

3) Increment all defined r(I,j)s

4) If r(i,j)=p(I,j), set r(i+1,j)=r(i,j), r(i,j)=0, e(j)=i. If p(i+1,j) is not defined, set p(i+1,j)=p(i,j)*

5) If no e(j)s have been set, for the largest defined j, set r(1,j+1)=r(1,j), p(1,j)=r(1,j), p(2,j)=p(1,j)*p(1,j), r(1,j)=0

6) repeat steps 2-5.

 

Example:

r(1,1)=1

p(1,1)=2
p(2,1)=4
r(1,1)=0 r(1,2)=2
r(2,1)=2
 e(1)=1                               -> 2= 2^1

p(1,1)=2 p(1,2)=3
p(2,1)=4 p(1,2)=9
r(1,1)=1 r(1,1)=0 r(1,2)=3
r(2,1)=3
          e(3)=1                      -> 3= 3^1

p(1,1)=2 p(1,2)=3
p(2,1)=4 p(1,2)=9
p(3,1)=8
r(1,1)=0 r(1,1)=1 r(1,2)=4
r(2,1)=0 r(2,2)=4
r(3,1)=4
 e(1)=2                               -> 4= 2^2

p(1,1)=2 p(1,2)=3 p(1,3)=5
p(2,1)=4 p(1,2)=9 p(1,3)=25
p(3,1)=8
r(1,1)=1 r(1,2)=2 r(1,3)=0  r(1,4)=5
r(2,1)=1 r(2,2)=5 r(2,3)=5
r(3,1)=5
                   e(3)=1             -> 5= 5^1

p(1,1)=2 p(1,2)=3 p(1,3)=5
p(2,1)=4 p(1,2)=9 p(1,3)=25
p(3,1)=8
r(1,1)=0 r(1,2)=0 r(1,3)=1  r(1,4)=6
r(2,1)=2 r(2,2)=6 r(2,3)=6
r(3,1)=6
  e(1)=1  e(2)=1                      -> 6= 2^1 * 3^1

p(1,1)=2 p(1,2)=3 p(1,3)=5  p(1,4)=7
p(2,1)=4 p(1,2)=9 p(1,3)=25 p(2,4)=49
p(3,1)=8
r(1,1)=1 r(1,2)=1 r(1,3)=2  r(1,4)=0  r(1,5)=7
r(2,1)=3 r(2,2)=7 r(2,3)=7
r(3,1)=7
                             e(4)=1   -> 7= 7^1

p(1,1)=2  p(1,2)=3 p(1,3)=5  p(1,4)=7
p(2,1)=4  p(1,2)=9 p(1,3)=25 p(2,4)=49
p(3,1)=8
p(4,1)=16
r(1,1)=0  r(1,2)=2 r(1,3)=3  r(1,4)=1  r(1,5)=8
r(2,1)=0  r(2,2)=8 r(2,3)=8
r(3,1)=0
r(4,1)=8
 e(1)=3                               -> 8= 2^3

p(1,1)=2  p(1,2)=3 p(1,3)=5  p(1,4)=7
p(2,1)=4  p(1,2)=9 p(1,3)=25 p(2,4)=49
p(3,1)=8
p(4,1)=16
r(1,1)=1  r(1,2)=0 r(1,3)=4  r(1,4)=2  r(1,5)=9
r(2,1)=1  r(2,2)=0 r(2,3)=9
r(3,1)=1  r(3,2)=9
r(4,1)=9
           e(2)=2                     -> 9= 3^2

p(1,1)=2  p(1,2)=3 p(1,3)=5  p(1,4)=7
p(2,1)=4  p(1,2)=9 p(1,3)=25 p(2,4)=49
p(3,1)=8
p(4,1)=16
r(1,1)=0  r(1,2)=1 r(1,3)=0  r(1,4)=3  r(1,5)=10
r(2,1)=2  r(2,2)=1 r(2,3)=10
r(3,1)=2  r(3,2)=10
r(4,1)=10
 e(1)=1             r(3)=1            -> 10= 2^1 * 5^1

Like PRMP, PRMPF isn’t of much practical use. The main virtue of these algorithms is the insight they provides into integer arithmetic when the integers are represented by their prime factorizations. More to come.

[Turtle]

Like PRMP, PRMPF isn’t of much practical use. The main virtue of these algorithms is the insight they provides into integer arithmetic when the integers are represented by their prime factorizations. More to come.

 

___I have printed up your posts/output Craig; this is fascinating work. It may take me some considerable time to step my way through & gain a more solid understanding. From your hints in some of our earlier integer math discussions I started thinking about substituting prime factorizations for some of my number lists; always more to try.

___This is in my view of considerable practical use inasmuch as one never suffers from too much insight. I love it! :circle:

[Turtle]

___I like this enlightening view & if I have understood correctly, I may have found a couple typos. (Bear with me as I don't quite understand using multiple quote tags; OK, not at all)

___Anyway, quoting from the first post paragraph:"...The Prime Remainder Method of generating the Primes (PRMP) - an algorithm for generating the primes using only “+1” and “=”:

Where:

p() is an array consisting of all the primes. e.g: p(1)=2, p(2)=3, p(3)=5, r(4)=7, etc.

r() is an array consisting of the modular remainder of a number divided by each prime. e.g: for the number 6, r(1)=0, r(2)=0, r(3)=1, r(4)=6 … r(greater than 4)=6..." I think the part I bold underlined should read "p(4)=7"

 

___In the output list in the third post: p(1,1)=2 p(1,2)=3 p(1,3)=5 p(1,4)=7

p(2,1)=4 p(1,2)=9 p(1,3)=25 p(2,4)=49

p(3,1)=8

p(4,1)=16

r(1,1)=0 r(1,2)=1 r(1,3)=0 r(1,4)=3 r(1,5)=10

r(2,1)=2 r(2,2)=1 r(2,3)=10

r(3,1)=2 r(3,2)=10

r(4,1)=10

e(1)=1 r(3)=1 -> 10= 2^1 * 5^1

 

___The bold/underline value; shouldn't this have 2 indices for r?

___Regarless of these minor errors, I like the approach & agree it may reveal more than it obscures. Keep it coming Craig! :circle:

[CraigD]

The line

p() is an array consisting of all the primes. e.g: p(1)=2, p(2)=3, p(3)=5, r(4)=7, etc.

does indeed contain a typo. It should read

p() is an array consisting of all the primes. e.g: p(1)=2, p(2)=3, p(3)=5, p(4)=7, etc.

The array notation is ugly, if very explicit. Note that in post #3, I dispense with it, and show successive r() arrays as a lists.

 

The description of PRMP is also ugly. Using a bit of English language common sense, it can be written:

1. Begin with a list R consisting of one entry equal to 1, and an empty list P.

2. Increment every entry in R

3. Compare every entry in R with the corresponding entry in P, replacing any that are equal with 0

4. If R contains no zeros, copy its last entry to the end of P and R, then replace it with 0

Repeat steps 2-4 ad-infinitum.

 

An annotated example:

P={},R={1} step 1

P={},R={2} step 2, step 3 no effect

P={2},R={0,2} step 4

P={2},R={1,3} step 2, step 3 no effect

P={2,3},R={1,0,3} step 4

P={2,3},R={2,1,4} step 2

P={2,3},R={0,1,4} step 3, step 4 no effect

P={2,3},R={1,2,5} step 2, step 3 no effect

P={2,3,5},R={1,2,0,5} step 4

P={2,3,5},R={2,3,1,6} step 2

P={2,3,5},R={0,0,1,6} step 3, step 4 no effect

P={2,3,5},R={0,0,1,6} step 3

P={2,3,5},R={1,1,2,7} step 2, step 3 no effect

P={2,3,5,7},R={1,1,2,0,7} step 4

… and so on.

 

It’s a pretty simple algorithm that my presentation may have made seem complicated.

 

Thanks for you input into my poor, lonely thread. It would appear I lack your flair for generating interest in arithmetic play. :circle:

[Turtle]

____ :circle: It's not flair but simple brute force. I note the threads you refer, I started in January & it is a stretch to claim a half dozen contributors including yourself. A tip of the hat to those brave souls by the way; they know who they are. :rant:

____ I very much like the style you present with the explicit nature as I sometimes have a hard time following otherwise. I certainly find this a very unique arena for sharing these topics, as compared to say exchanging letters or carrying on in the standard academic peer review/publish process.

___Let's rock & bring it on & I'll feed the ugly red-headed step kids. I don't know if explicit is always ugly, but ugly is always explicit. I am cooking up a little ugly list of the prime factorizations of the Strange Numbers & this little duckling of yours may yet grow to swanhood.

[CraigD]

…

___I may have missed something, but I don't see all. E.g. in the line:

1012 123 5inf)

 

Isn't there also a 114?

The algorithm never includes a representation of N4, because when N is represented by

1002 113 4

One of the representations (1002) has a 0 in its one’s place, so the condition in step 3 is false.

 

Without this condition, the algorithm generates the Natural numbers greater than 2, but the factorization don’t produce the number unless it is prime. The factorizations produce this odd looking sequence

2
3 16
5 36
7 256 81 100
11 3456
13 196 225 32768
17 17496
19 16000 441 484
23 1327104 625 676 6561 43904
29 810000
31 2097152 1089 1156 1225 362797056
37 1444 1521 10240000
41 3111696
43 170368 273375 2116
47 8153726976 2401 625000 2601 281216
53 76527504 3025 39337984 3249 3364
59 93312000000
61 3844 750141 8589934592 4225 18974736
67 628864 4761 24010000
71 10030613004288
73 5476 2109375 877952 5929 37015056
79 104857600000 14348907 6724
83 702596063232 7225 7396 7569 239878144
89 1594323000000 8281 1557376 8649 8836 9025 50096498540544
97 6588344 2910897 100000000000
…

I can’t see that it’s good for much but a Math riddle, but one can never tell.

 

I enjoy your posts, and am glad to be able to reciprocate. In my short time here, this has become one of my favorite web forums. ;)

[Turtle]

___I do love an exhaustive list! ;) ;)

 

___I may have missed something, but I don't see all. E.g. in the line:

1012 123 5inf)

 

Isn't there also a 114?

___In any case, it is a facinating bit of work here! I continue to study your algorithms & printouts of their output for my own elucidation. Thanks!

[Doctordick]

Just a note to let you know someone else is following this thread. ;) At the moment I have nothing to add but if I see anything which seems pertinent I'll let you know. Meanwhile keep up the good work. I am not being careful in my reading but I follow what you are saying and did catch the early typos.

 

Have fun -- Dick

 

Knowledge is Power

and the most common abuse of that power is to use it to hide stupidity