Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] (unknown)

Expand Messages
  • Phil Carmody
    ... {u=3;m=4000;v=u+m;forstep(a=u,v,2,t=a^2-2;c=ceil(sqrt(t/2));for(n=c,a-2,s=2*n^2-t;if(issquare(s),next(2)));print(t))} ... This is not instantly obvious,
    Message 1 of 2 , Oct 17, 2006
      --- Robin Garcia <sopadeajo2001@...> wrote:
      > Here is a Pari program to find all the primes of the form a^2-2
      >
      >
      {u=3;m=4000;v=u+m;forstep(a=u,v,2,t=a^2-2;c=ceil(sqrt(t/2));for(n=c,a-2,s=2*n^2-t;if(issquare(s),next(2)));print(t))}
      >
      > u must always be odd for the program to work.
      > Choose the range you want from u odd to u+m
      >
      > Can you say how the algoritm works?
      > Can you prove that this algoritm always works?

      This is not instantly obvious, but on re-arranging the terms it drops out quite
      easily. Your test doesn't just work for primes of the form a^2-2, but any value
      of the form 8N+7, of which the above is a subset.

      It relies on 2*x^2-y*2 being the canonical 8N+7 quadratic form.
      See Atkin/Bernstein's Prime Sieves (primegen) paper.

      Phil

      () ASCII ribbon campaign () Hopeless ribbon campaign
      /\ against HTML mail /\ against gratuitous bloodshed

      [stolen with permission from Daniel B. Cristofani]

      __________________________________________________
      Do You Yahoo!?
      Tired of spam? Yahoo! Mail has the best spam protection around
      http://mail.yahoo.com
    Your message has been successfully submitted and would be delivered to recipients shortly.