Sorry, an error occurred while loading the content.

Expand Messages
• 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]
• ... {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.