Expand Messages
• ... A simple optimisation follows from your post: If gcd(pr+1,ps) 1 then gcd(pr+1,ps) must be f[l,1] (the largest prime factor of ps). So gcd(pr+1,ps) 1 can be
Message 1 of 3 , Oct 8, 2008
• 0 Attachment
Phil Carmody wrote:
> i=0;ps=0;pr=1;pend=1;p=1;while(p<400000000,i++;p=nextprime(p+1);
> ps+=p;if(i%10000==0,print(i" "p));f=factor(ps);l=length(f~);
> if(f[l,1]>p,pr*=pend*p;pend=1;if((g=gcd(pr+1,ps))>1,
> print(i" "p" "ps" "factor(ps)" "g)),pend*=p))

A simple optimisation follows from your post:
If gcd(pr+1,ps)>1 then gcd(pr+1,ps) must be f[l,1] (the largest
prime factor of ps).
So gcd(pr+1,ps)>1 can be replaced by the faster (pr+1)%f[l,1]==0.
In my timings, using pr%f[l,1]==f[l,1]-1 was a few percent faster than
(pr+1)%f[l,1]==0.
I have tested to n=1000000, p=15485863 with no new solution.

> (The optimisation of only performing the * and % when there's
> possible factor did save a small amount of time. This technique
> might be amenable to a tree-sieve and fewer bigger multiplies. Jens?)

Yes, a tree-sieve should make it much faster but I'm not spending time
implementing it.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.