Browse Groups

• 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 3:38 PM
View Source
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
• ... 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, 2012
View Source
--- 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.
>
>
> 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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.