Prime Numbers formula !!

[applePi]

i am trying to check that this formula produce prime numbers

Code: Select all

(k + 2)* (1 - (w*z + h + j - q)^2 - ((g*k + 2*g + k + 1)*(h + j) + h - z)^2 - (2*n + p + q + z - e)^2 
-(16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 - f^2)^2 - (e^3*(e + 2)*(a + 1)^2 + 1 - o^2)^2 - ((a^2 - 1)*y^2 + 1 - x^2)^2 
-(16*r^2*y^4*(a^2 - 1) + 1 - u^2)^2 - (((a + u^2*(u^2 - a))^2 - 1)*(n + 4*d*y)^2 + 1 - (x + c*u)^2)^2 - (n + L + v - y)^2
-((a^2 - 1)*L^2 + 1 - m^2)^2 - (a*i + k + 1 - L - i)^2 - (p + L*(a - n - 1) + b*(2*a*n + 2*a - n^2 - 2*n - 2) - m)^2
-(q + y*(a - p - 1) + s*(2*a*p + 2*a - p^2 - 2*p - 2) - x)^2 - (z + p*L*(a - p) + t*(2*a*p - p^2 - 1) - p*m)^2)

as said by its discoverer in article "diophantine representation of the set of prime numbers":
https://www.maa.org/sites/default/files ... aWiens.pdf

and deleting the new lines we get:

Code: Select all

(k + 2)* (1 - (w*z + h + j - q)^2 - ((g*k + 2*g + k + 1)*(h + j) + h - z)^2 - (2*n + p + q + z - e)^2 -(16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 - f^2)^2 - (e^3*(e + 2)*(a + 1)^2 + 1 - o^2)^2 - ((a^2 - 1)*y^2 + 1 - x^2)^2 -(16*r^2*y^4*(a^2 - 1) + 1 - u^2)^2 - (((a + u^2*(u^2 - a))^2 - 1)*(n + 4*d*y)^2 + 1 - (x + c*u)^2)^2 - (n + L + v - y)^2-((a^2 - 1)*L^2 + 1 - m^2)^2 - (a*i + k + 1 - L - i)^2 - (p + L*(a - n - 1) + b*(2*a*n + 2*a - n^2 - 2*n - 2) - m)^2-(q + y*(a - p - 1) + s*(2*a*p + 2*a - p^2 - 2*p - 2) - x)^2 - (z + p*L*(a - p) + t*(2*a*p - p^2 - 1) - p*m)^2)

then we need the Little John tool to convert '^' to PB/C Pow, http://purebasic.fr/english/viewtopic.p ... 25#p464248 so we get this:

Code: Select all

(k+2)*(1-Pow(w*z+h+j-q,2)-Pow((g*k+2*g+k+1)*(h+j)+h-z,2)-Pow(2*n+p+q+z-e,2)-Pow(16*Pow(k+1,3)*(k+2)*Pow(n+1,2)+1-Pow(f,2),2)-Pow(Pow(e,3)*(e+2)*Pow(a+1,2)+1-Pow(o,2),2)-Pow((Pow(a,2)-1)*Pow(y,2)+1-Pow(x,2),2)-Pow(16*Pow(r,2)*Pow(y,4)*(Pow(a,2)-1)+1-Pow(u,2),2)-Pow((Pow(a+Pow(u,2)*(Pow(u,2)-a),2)-1)*Pow(n+4*d*y,2)+1-Pow(x+c*u,2),2)-Pow(n+L+v-y,2)-Pow((Pow(a,2)-1)*Pow(L,2)+1-Pow(m,2),2)-Pow(a*i+k+1-L-i,2)-Pow(p+L*(a-n-1)+b*(2*a*n+2*a-Pow(n,2)-2*n-2)-m,2)-Pow(q+y*(a-p-1)+s*(2*a*p+2*a-Pow(p,2)-2*p-2)-x,2)-Pow(z+p*L*(a-p)+t*(2*a*p-Pow(p,2)-1)-p*m,2))

the author said :[[ (1) is a polynomial of degree 25 in 26 variables, a, b, c,..., z. When nonnegative integers are substituted for these variables, the positive values of (1) coincide exactly with the set of all prime numbers 2,3,5,.... The polynomial (1) also takes on negative values, e.g., - 76.]]

in page 200 of the book music of the primes the author said: [[This formula works like a computer program. You randomly change the letters A, . . ., Z into numbers and then use the formula to perform a calculation on those numbers; for example, you might choose A = 1, B = 2, . . ., Z = 26. If the answer is bigger than zero, then the result of the
calculation is prime.]]

applying the second author advice: the following program does not produce positive numbers at all. another source of the formula in https://en.wikipedia.org/wiki/Formula_for_primes
so it is either the formula or the program or my understanding of the issue are wrong.

Code: Select all

For counter=1 To 100000
  A=Random(50, 1)
  B=Random(50, 1)
  C=Random(50, 1)
  D=Random(50, 1)
  E=Random(50, 1)
  F=Random(50, 1)
  G=Random(50, 1)
  H=Random(50, 1)
  I=Random(50, 1)
  J=Random(50, 1)
  K=Random(50, 1)
  L=Random(50, 1)
  M=Random(50, 1)
  N=Random(50, 1)
  O=Random(50, 1)
  P=Random(50, 1)
  Q=Random(50, 1)
  R=Random(50, 1)
  S=Random(50, 1)
  T=Random(50, 1)
  U=Random(50, 1)
  V=Random(50, 1)
  W=Random(50, 1)
  X=Random(50, 1)
  Y=Random(50, 1)
  Z=Random(50, 1)
  
 
  res.q = (k+2)*(1-Pow(w*z+h+j-q,2)-Pow((g*k+2*g+k+1)*(h+j)+h-z,2)-Pow(2*n+p+q+z-e,2)-Pow(16*Pow(k+1,3)*(k+2)*Pow(n+1,2)+1-Pow(f,2),2)-Pow(Pow(e,3)*(e+2)*Pow(a+1,2)+1-Pow(o,2),2)-Pow((Pow(a,2)-1)*Pow(y,2)+1-Pow(x,2),2)-Pow(16*Pow(r,2)*Pow(y,4)*(Pow(a,2)-1)+1-Pow(u,2),2)-Pow((Pow(a+Pow(u,2)*(Pow(u,2)-a),2)-1)*Pow(n+4*d*y,2)+1-Pow(x+c*u,2),2)-Pow(n+L+v-y,2)-Pow((Pow(a,2)-1)*Pow(L,2)+1-Pow(m,2),2)-Pow(a*i+k+1-L-i,2)-Pow(p+L*(a-n-1)+b*(2*a*n+2*a-Pow(n,2)-2*n-2)-m,2)-Pow(q+y*(a-p-1)+s*(2*a*p+2*a-Pow(p,2)-2*p-2)-x,2)-Pow(z+p*L*(a-p)+t*(2*a*p-Pow(p,2)-1)-p*m,2))       
  If res >= 0
    Debug res
    Debug k+2
  EndIf
  ;Debug a: Debug t
  ;Debug res
Next
Debug "end"


  
  

[wilbert]

Wow, that seems complicated.
I wouldn't use the Pow procedure for this since it operates on floats and therefore returns an inaccurate result.
If the formula is right and only produces prime numbers, you can't be sure that it still returns only prime numbers when using floats.
Since it only needs ^2, ^3 and ^4 you could create custom procedures Pow2, Pow3 and Pow4 that operate on quads instead.

[applePi]

Thanks wilbert , i think now the float are not necessary since i don't see other than( + - * ^ ) so changing in the yet not working code the a.f to a and so on, the res.f to res.q (i never used quad before)
the problem all authors provide the formula with some error in it such as this:
https://books.google.co.uk/books?id=TJu ... rs&f=false
the second line from the bottom of the equation have q+L(a - n - 1) while it is (q + y*(a - p - 1)
and the third line from the bottom of the equation have no power at the end, and he ask the readers to try programming the desktop computer with this polynomial
i saw other errors in other books and seems no one have tried it in a computer before.
i will try several programming languages to see if the problem are not with the positions of Pow but in the implementation of the idea.

[applePi]

i have tried powerbasic console v6, but it does not support more than 256 chars per line even if we tried pbcc.exe primes.bas it will give error. i find it clumsy to divide the long line to many partitions.
then i have tried mathematica version 8 and then using a value of 3 for a,b,c,..., z using the formula above but using '^' (look the page top) the result is
-122098310350105
now using purebasic with a,b,c,...z = 3 the result is the same
-122098310350105
so i think the Purebasic formula with pow are the exact implementation of the formula with '^' thanks for Little John
now have tried this code in mathematica using random numbers between 1 to 50 for every variable, running over 10000 times but all results is negatives big numbers.
the 2ed of the google book mentioned above have deleted the reference to this formula.

mathematica code (note that it is case sensitive so L is not l , i use mathematica only occasional, once per a year)

Code: Select all

counterx=1;While[counterx<10000,
a = RandomInteger[{1,50}];
b = RandomInteger[{1,50}];
c = RandomInteger[{1,50}];
d = RandomInteger[{1,50}];
e = RandomInteger[{1,50}];
f = RandomInteger[{1,50}];
g = RandomInteger[{1,50}];
h = RandomInteger[{1,50}];
i = RandomInteger[{1,50}];
j = RandomInteger[{1,50}];
k = RandomInteger[{1,50}];
L = RandomInteger[{1,50}];
m = RandomInteger[{1,50}];
n = RandomInteger[{1,50}];
o = RandomInteger[{1,50}];
p = RandomInteger[{1,50}];
q = RandomInteger[{1,50}];
r = RandomInteger[{1,50}];
s = RandomInteger[{1,50}];
t = RandomInteger[{1,50}];
u = RandomInteger[{1,50}];
v = RandomInteger[{1,50}];
w = RandomInteger[{1,50}];
x = RandomInteger[{1,50}];
y = RandomInteger[{1,50}];
z = RandomInteger[{1,50}];
res = (k+2)*(1-(w*z+h+j-q)^2-((g*k+2*g+k+1)*(h+j)+h-z)^2-(2*n+p+q+z-e)^2-(16*(k+1)^3*(k+2)*(n+1)^2+1-f^2)^2-(e^3*(e+2)*(a+1)^2+1-o^2)^2-((a^2-1)*y^2+1-x^2)^2-(16*r^2*y^4*(a^2-1)+1-u^2)^2-(((a+u^2*(u^2-a))^2-1)*(n+4*d*y)^2+1-(x+c*u)^2)^2-(n+L+v-y)^2-((a^2-1)*L^2+1-m^2)^2-(a*i+k+1-L-i)^2-(p+L*(a-n-1)+b*(2*a*n+2*a-n^2-2*n-2)-m)^2-(q+y*(a-p-1)+s*(2*a*p+2*a-p^2-2*p-2)-x)^2-(z+p*L*(a-p)+t*(2*a*p-p^2-1)-p*m)^2);Print[res]; counterx++]

a few results:
-871892724237847827550180809390
-404543797346504689070548991881132605684696
-14743883715170969654461726529040
-843556207417698065552038366459891310844
-35580678562157269619153204197914682680
-16816382106809212269220281376537855671
-377167761441202468367355149530
-12893131040235052002704366113683222588
-494905320286029387076213405199416068
-84902767039180066990183594094554165
-18453330569524387216872925309021983517111008
-1598545819242707466719110903830638520197475

Edit: another Doc: chapter 2 page 39-40 from the book:
Prime Numbers and Computer Methods for Factorization
http://www.springer.com/cda/content/doc ... 972-c1.pdf

[wilbert]

Any even number is clearly not a prime since it can be divided by 2 so something seems wrong.

[sancho2]

2 is a prime number.
However every number this formula as implemented by applePi is a negative number which are not prime numbers:

Prime number is a positive natural number that has only two positive natural number divisors - one and itself.

It looks like this forumla is comprised of this set:

Formula based on a system of Diophantine equations

https://en.wikipedia.org/wiki/Formula_for_primes
Its a monster to compose and compare, good luck.

[Little John]

2 is a prime number.

This is the only exception from the rule which wilbert mentioned.

[sancho2]

I did some initial formula comparison. There might be a problem right off:

Code: Select all

    
  ; first equation looks right 
   ;(k+2) (1 - 
   ; [wz + h + j - q]^2 - 
   (k + 2) * (1 - (w*z + h + j - q)^2 -
    
   ; second equation looks right
   ; [(gk + 2g + k + 1)(h + j) + h - z]^2 -
   ((g*k + 2*g + k + 1)*(h + j) + h - z)^2 -
    
   ; third equation is out of place according to the wiki page
   ; [16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2]^2 - 
   (2*n + p + q + z - e)^2
   
   ; there may be more out of place

I am not a math guy so I am only guessing that the order of operations get screwed up when the equations are not followed in order.
On reading that page numerous times it seems that when the result is positive the result is a prime number. This may take more than the 100,000 iterations in your loop.
[edit]
If you are still working on this, I would be very curious as to the values of a through z, and the resulting prime when you hit your first prime number.

[edit2]
Here is an attempt at wikipedias formula for primality. I am unsure if I am using these quad variables accurately. Do the larger numbers work with mod? They seem to.
I tested the numbers from 1 to 20,000 using this formula and compared to a brute force while loop and it seems to work. Note that 20,000 numbers output to debug takes my machine approx. 7.5k milliseconds.

Code: Select all

Procedure.i IsPrime(myNum.q)
  Protected x.q
  
  If myNum <= 3 
    ProcedureReturn Bool(myNum > 1)
  EndIf
  
  If (Mod(myNum, 2) = 0) Or (Mod(myNum, 3) = 0)
    ProcedureReturn 0
  EndIf
  
  x = 5 
  While x * x <= myNum
    If (Mod(myNum,x) = 0) Or (Mod(myNum,(x + 2)) = 0)
      ProcedureReturn 0
    EndIf
    
    x = x + 6
  Wend
  
  ProcedureReturn 1
  
  
EndProcedure

1 to 20,000 = 2262 prime numbers, last one being 19997

Code: Select all

For n = 1 To 20000
  Debug n
  If IsPrime(n) 
    c = c + 1
    Debug "prime" + Str(n)
  EndIf
  
Next

[applePi]

sancho2 writes: order of operations get screwed up when the equations are not followed in order

i have noticed the different versions but in fact it is the same james jones formula: it is made from 14 formulas every one preceded as a whole by '-' and any where we put it will not make a difference, as a proof : the wiki formula are copied (or vice versa) from the book "Prime Numbers and Computer Methods for Factorization" page 39 look its chapter 2 springer link above

here is the original formula and the wiki formula will produce the same result if we replace every variable by 1 or 2 or 3, but using 4 there is a diffrendce
-189322035734168800
-189322035734168832
using 5 or more
-9223372036854775808
-9223372036854775808
this is the limits of numbers in all prog. languages, http://www.purebasic.com/documentation/ ... ables.html, so we must use big numbers library such as GMP http://purebasic.fr/english/viewtopic.php?f=12&t=61315 i will learn how to use it in this context.
so my usage above for values 50 to 1 are partially useless, it is a show case .

Code: Select all

  A=3
  B=3
  C=3
  D=3
  E=3
  F=3
  G=3
  H=3
  I=3
  J=3
  K=3
  L=3
  M=3
  N=3
  O=3
  P=3
  Q=3
  R=3
  S=3
  T=3
  U=3
  V=3
  W=3
  X=3
  Y=3
  Z=3
  
  ; from the james jones original paper
  ;(k + 2)* (1 - (w*z + h + j - q)^2 - ((g*k + 2*g + k + 1)*(h + j) + h - z)^2 - (2*n + p + q + z - e)^2 -(16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 - f^2)^2 - (e^3*(e + 2)*(a + 1)^2 + 1 - o^2)^2 - ((a^2 - 1)*y^2 + 1 - x^2)^2 -(16*r^2*y^4*(a^2 - 1) + 1 - u^2)^2 - (((a + u^2*(u^2 - a))^2 - 1)*(n + 4*d*y)^2 + 1 - (x + c*u)^2)^2 - (n + L + v - y)^2-((a^2 - 1)*L^2 + 1 - m^2)^2 - (a*i + k + 1 - L - i)^2 - (p + L*(a - n - 1) + b*(2*a*n + 2*a - n^2 - 2*n - 2) - m)^2-(q + y*(a - p - 1) + s*(2*a*p + 2*a - p^2 - 2*p - 2) - x)^2 - (z + p*L*(a - p) + t*(2*a*p - p^2 - 1) - p*m)^2)
  ;from wiki page or say from the book (Prime Numbers and Computer Methods for Factorization)
  ;(k + 2)* (1 - (w*z + h + j - q)^2 - ((g*k + 2*g + k + 1)*(h + j) + h - z)^2 -(16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 - f^2)^2 - (2*n + p + q + z - e)^2 -(e^3*(e + 2)*(a + 1)^2 + 1 - o^2)^2 - ((a^2 - 1)*y^2 + 1 - x^2)^2 -(16*r^2*y^4*(a^2 - 1) + 1 - u^2)^2 - (n + L + v - y)^2-((a^2 - 1)*L^2 + 1 - m^2)^2 - (a*i + k + 1 - L - i)^2 -(((a + u^2*(u^2 - a))^2 - 1)*(n + 4*d*y)^2 + 1 - (x + c*u)^2)^2 -(p + L*(a - n - 1) + b*(2*a*n + 2*a - n^2 - 2*n - 2) - m)^2 -(q + y*(a - p - 1) + s*(2*a*p + 2*a - p^2 - 2*p - 2) - x)^2 -(z + p*L*(a - p) + t*(2*a*p - p^2 - 1) - p*m)^2)
  res.q = (k+2)*(1-Pow(w*z+h+j-q,2)-Pow((g*k+2*g+k+1)*(h+j)+h-z,2)-Pow(2*n+p+q+z-e,2)-Pow(16*Pow(k+1,3)*(k+2)*Pow(n+1,2)+1-Pow(f,2),2)-Pow(Pow(e,3)*(e+2)*Pow(a+1,2)+1-Pow(o,2),2)-Pow((Pow(a,2)-1)*Pow(y,2)+1-Pow(x,2),2)-Pow(16*Pow(r,2)*Pow(y,4)*(Pow(a,2)-1)+1-Pow(u,2),2)-Pow((Pow(a+Pow(u,2)*(Pow(u,2)-a),2)-1)*Pow(n+4*d*y,2)+1-Pow(x+c*u,2),2)-Pow(n+L+v-y,2)-Pow((Pow(a,2)-1)*Pow(L,2)+1-Pow(m,2),2)-Pow(a*i+k+1-L-i,2)-Pow(p+L*(a-n-1)+b*(2*a*n+2*a-Pow(n,2)-2*n-2)-m,2)-Pow(q+y*(a-p-1)+s*(2*a*p+2*a-Pow(p,2)-2*p-2)-x,2)-Pow(z+p*L*(a-p)+t*(2*a*p-Pow(p,2)-1)-p*m,2))       
  
  Debug res
  
  res.q = (k+2)*(1-Pow(w*z+h+j-q,2)-Pow((g*k+2*g+k+1)*(h+j)+h-z,2)-Pow(16*Pow(k+1,3)*(k+2)*Pow(n+1,2)+1-Pow(f,2),2)-Pow(2*n+p+q+z-e,2)-Pow(Pow(e,3)*(e+2)*Pow(a+1,2)+1-Pow(o,2),2)-Pow((Pow(a,2)-1)*Pow(y,2)+1-Pow(x,2),2)-Pow(16*Pow(r,2)*Pow(y,4)*(Pow(a,2)-1)+1-Pow(u,2),2)-Pow(n+L+v-y,2)-Pow((Pow(a,2)-1)*Pow(L,2)+1-Pow(m,2),2)-Pow(a*i+k+1-L-i,2)-Pow((Pow(a+Pow(u,2)*(Pow(u,2)-a),2)-1)*Pow(n+4*d*y,2)+1-Pow(x+c*u,2),2)-Pow(p+L*(a-n-1)+b*(2*a*n+2*a-Pow(n,2)-2*n-2)-m,2)-Pow(q+y*(a-p-1)+s*(2*a*p+2*a-Pow(p,2)-2*p-2)-x,2)-Pow(z+p*L*(a-p)+t*(2*a*p-Pow(p,2)-1)-p*m,2))
  
  Debug res
  

it is said that the above formula in fact like this one (k+2)*(1 - M) look this argument from the book : What Is Mathematics?: An Elementary Approach (page 488):
[[ The positive values of this expression, for integer values of a, ..., z,
are precisely the primes.
There is an apparent paradox: the expression clearly factorizes. Indeed it is of the form (k+ 2) {1 - M). However, M is a sum of squares, so the expression is positive if and only if M = 0, and its value is then k + 2. So the polynomial M has to be constructed so that
M(k, other variables) = 0 if and only if k + 2 is prime. ]]

the author of the springer book said: The polynomial also yields negative values (as a matter of fact it does so for most values of the variables), but these are not necessarily (negative) primes.

note: me too is not a mathematician, i just find this subject funny and deserve investigation. surely more about the subject later.

[collectordave]

Hi All

Just thought I would add a little more to this.

The download is a prime number generator which checks the time it takes to generate prime numbers from a start to an end value entered by the user. It also includes two checking routines, one checks that the numbers genereated are prime numbers and the second checks that the prime numbers between the entered values are included in the generated primes by comparing the list of numbers generated against an included database of prime numbers.

The database only includes prime numbers from 1 to 100000, I can add more if required.

You can replace the GenPrimes() procedure with your own to check on speed etc.

The code and database can be found here:-https://github.com/collectordave/PureBasic-PrimeNumbers

Enjoy

cd