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

Re: number of selfridges?

Expand Messages
  • paulunderwooduk
    I tested with pari-gp to n=5*10^9: { for(n=7,5000000000, if(n%50000000==0,print(n)); if(gcd(n,30)==1&&!issquare(n)&&!isprime(n),
    Message 1 of 46 , Dec 9, 2011
    View Source
    • 0 Attachment
      I tested with pari-gp to n=5*10^9:

      {
      for(n=7,5000000000,
      if(n%50000000==0,print(n));
      if(gcd(n,30)==1&&!issquare(n)&&!isprime(n),
      x=1;while(kronecker(x^2-4,n)!=-1,x=x+1);
      if(Mod(Mod(1,n)*(l*x-3),l^2-x*l+1)^((n+1))+2*x^2-9==0,
      print(n" "x))))
      }

      I converted the following to GMP with the use of a nextprime sieve from Vincent Diepeveen, taking x^2-3 outside of the loop:

      {
      if(gcd(n,30)==1&&!issquare(n),
      x=1;while(kronecker(x^2-4,n)!=-1,x=x+1);
      bin=binary(n+1);ln=length(bin);
      a=x;b=-3;
      for(i=2,ln,
      na=a*(x*a+2*b);b=((b-a)*(b+a))%n;a=na%n;
      if(bin[i],
      na=(x^2-3)*a+x*b;b=-(x*a+3*b)%n;a=na%n));
      print(a==0&&Mod(b,n)==9-2*x^2))
      }

      The new GMP test program runs ~14 times quicker than the pari-gp code. I can crunch about 2*10^9 in a 3.6GHz hour.

      Without finding a counterexample (to this 2-selfridge test), I have now reached 10^10. I'll take it up to 10^11...

      Paul
    • paulunderwooduk
      ... Combining fails with the composite counterexample n=256999 and x=32768, However, I have tested the 1+1+1+2 conjecture up to n
      Message 46 of 46 , Apr 14 10:19 AM
      View Source
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        >
        >
        >
        > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
        > >
        > > Hi,
        > >
        > > I have added a Fermat test to make a 1+1+1+2 selfridge test:
        > >
        > > For N>5, with gcd(6,N)==1, find an integer x:
        > > gcd(x^3-x,N)==1
        > > kronecker(x^2-4,N)==-1
        > >
        > > and check:
        > > (x+2)^((N-1)/2)==kronecker(x+2,N) (mod N) (Euler)
        > > (x-2)^((N-1)/2)==kronecker(x-2,N) (mod N) (Euler)
        > > x^(N-1)==1 (mod N) (Fermat)
        > > L^(N+1) == 1 (mod N, L^2-x*L+1) (Lucas)
        > >
        >
        > Note: I should say gcd(30,N)==1 because gcd(x^3-x,N)==1 and kronecker(x^2-4,n)==-1.
        >
        > Re: http://tech.groups.yahoo.com/group/primenumbers/message/24090?l=1
        >
        > Now consider combining the 2 Euler tests with the Lucas test:
        >
        > (L*D)^((n+1)/2)==D (mod N, L^2-x*L+1) (D=x^2-4.)
        >
        > with the restriction kronecker(x+2,N)==-1.
        >
        > These together with the Fermat test makes for a 1+2-selfridge test.
        >
        > Can you find a counterexample?
        >
        > So far the near-refutation from Pinch's carmichael list is:
        > N,x,gcd(x^2-1)
        > ------------------
        > 1909001 884658 1909001
        >
        > Paul
        >

        Combining fails with the composite counterexample n=256999 and x=32768, However, I have tested the 1+1+1+2 conjecture up to n<10^7,

        Paul -- restoring symmetry
      Your message has been successfully submitted and would be delivered to recipients shortly.