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

Expand Messages
  • Robin Garcia
    Here is a Pari program to find all the primes of the form a^2-2
    Message 1 of 2 , Oct 17, 2006
    • 0 Attachment
      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?


      ---------------------------------

      LLama Gratis a cualquier PC del Mundo.
      Llamadas a fijos y móviles desde 1 céntimo por minuto.
      http://es.voice.yahoo.com

      [Non-text portions of this message have been removed]
    • 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 2 of 2 , Oct 17, 2006
      • 0 Attachment
        --- 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.