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

Re: puzzle for a counterexample

Expand Messages
  • djbroadhurst
    ... In 3.5 GHz-hours, the gremlins found 33,445 counterexamples. Since Kermit likes big files of semiprimes, the results are in
    Message 1 of 66 , Nov 2, 2012
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "bhelmes_1" <bhelmes@> wrote:

      > 1. gcd (a, p)=1
      > 2. Let jacobi (a, p) = -1
      > 3. let jacobi (a^2-a, p)=-1
      > 4. a^[(p-1)/2]=-1 mod p
      > 5. if (a+sqrt (a))^p = a-sqrt(a) mod p
      > 6. s+t*sqrt(a):=(a+sqrt (a))^[(p+1)/2] implies that
      > gcd (s, p)=1 or 0 or p, and gcd (t, p)=1 or 0 or p.

      In 3.5 GHz-hours, the gremlins found 33,445 counterexamples.

      Since Kermit likes big files of semiprimes, the results are in
      http://physics.open.ac.uk/~dbroadhu/cert/underbh4.txt

      They all fool Bernhard's 4-selfridge test, above, with my
      strengthening: s = 0 mod p, gcd(t,p) = 1, as shown here:

      {tst(p,a)=local(u,v,s,t);
      if(gcd(a,p)==1&&kronecker(a,p)==-1&&
      kronecker(a^2-a,p)==-1&&Mod(a,p)^((p-1)/2)==-1,
      u=Mod(Mod(1,p)*(a+x),x^2-a);
      if(u^p==a-x,v=lift(lift(u^((p+1)/2)));
      s=polcoeff(v,0);t=polcoeff(v,1);
      if(s||gcd(t,p)-1,t=0)));t;}

      {tstfile(file)=local(c,d,n,a,v=readvec(file));
      for(k=1,#v,n=v[k][1];a=v[k][2];
      if(tst(n,a)&&!isprime(n),c++;if(n%4==1,d++)));
      print1(c" counterexamples in "file" : ");
      print(round(100*d/c)"% with n = 1 mod 4");}

      tstfile("underbh4.txt");

      33445 counterexamples in underbh4.txt : 46% with n = 1 mod 4

      David (per proxy the industrious gremlins)
    • djbroadhurst
      ... Here are some scores out of 5: {A(k,x)=sum(j=0,k/2,(-1)^j*binomial(k-j,j)*x^(k-2*j));} {B(k,x)=sum(j=0,(k-1)/2,(-1)^j*binomial(k-j-1,j)*x^(k-2*j-1));}
      Message 66 of 66 , Nov 22, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        paulunderwooduk" <paulunderwood@...> wrote:

        > At least one of the evaluations of x at -1,1,0,-2 or 2
        > should be -1,1,0,-2, or 2

        Here are some scores out of 5:

        {A(k,x)=sum(j=0,k/2,(-1)^j*binomial(k-j,j)*x^(k-2*j));}
        {B(k,x)=sum(j=0,(k-1)/2,(-1)^j*binomial(k-j-1,j)*x^(k-2*j-1));}
        {L=[-1,1,0,-2,2];S=Set(L);for(k=2,40,f=factor(A(k,x)-B(k,x))[,1];
        g=f[#f];c=0;for(j=1,#L,if(setsearch(S,subst(g,x,L[j])),c++));
        print1(c","));}

        4,4,3,4,4,4,4,4,4,4,4,3,4,4,4,5,4,4,4,4,5,4,4,4,4,5,4,4,4,5,5,4,4,4,4,4,5,4,3,

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.