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

Re: [PrimeNumbers] Coprimes Puzzle

Expand Messages
  • Jens Kruse Andersen
    ... 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.