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

Re: final corrections for T-Sequence

Expand Messages
  • djbroadhurst
    ... Ken has already told you that there are 5 pseudoprimes less than 10^6. Here I write your algorithm in Pari-GP and generate these 5, with their
    Message 1 of 4 , Oct 19, 2010
    View Source
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      Bill Bouris <leavemsg1@...> wrote:

      > if I could just get my act together, then my program might be
      > successful

      Ken has already told you that there are 5 pseudoprimes
      less than 10^6. Here I write your algorithm in Pari-GP
      and generate these 5, with their factorizations and
      false witnesses, by exhaustion:

      {bin(N)=local(A=[N,(N+1)/2,(N-1)/2],b,c,t=1,i=1);
      while(t,i+=2;b=A[i]%2;if(A[i]<3,t=0;A=concat(A,if(b,0,[1,0])),
      c=(A[i-1]+1-b)/2;A=concat(A,[c,c-1])));A;}

      {lucas(N,A,L)=local(T=Mod([2,L,L^2-2],N),T3,K,F,Z=[],t);
      forstep(j=#A-3,1,-1,if(A[j]%2,K=if(A[j]==A[j+1]+A[j+2],0,1);
      T3=T[3-K]*T[2-K]-L,T3=T[2]^2-2);if(T3==2&&j-2,F=j;break());
      if(j>1&&j<4,Z=concat(Z,T3^2-2));T=[T[2],T[3],T3]);
      if(!F,t=T3==L&&(Z==[2,L^2-2]||Z==[L^2-2,2]));[F,t];}

      {bill(N)=local(A,L=2,P=[],t); \\ for odd N > 5
      if(gcd(N,15)==1,A=bin(N);while(#P<2,L++;t=lucas(N,A,L);
      if(!t[1],if(t[2],P=concat(P,L),P=[];break()))));P;}

      {forstep(N=7,10^6,2,P=bill(N);
      if(isprime(N)!=(#P==2),print([N,factor(N)[,1]~,P])));}

      [80189, [17, 53, 89], [3, 4]]
      [84419, [29, 41, 71], [3, 4]]
      [721801, [601, 1201], [3, 4]]
      [737471, [7, 137, 769], [3, 4]]
      [873181, [661, 1321], [3, 4]]

      Comments:

      1) My code is modelled on Bill's and hence is very inefficient.
      It is notable that Bill requires 55 Lucas tests to conclude
      that 1412759 is probably prime:

      print(bill(1412759));

      [39, 57]

      since L = 39 and L = 57 are the smallest witnesses L > 2
      such that he is prepared to accept the result.
      He thus uses 110 selfridges, where BPSW would use only 3.

      2) It is easy to find larger pseudoprimes.
      Here are 5 greater than 2*10^9:

      fooled=[2023351681,2050864921,2099611801,2189197501,2201924341];
      for(k=1,5,N=fooled[k];print([factor(N)[,1]~,bill(N)]));

      [[13, 41, 71, 127, 421], [3, 4]]
      [[7, 17, 19, 521, 1741], [3, 4]]
      [[7, 53, 131, 43201], [3, 4]]
      [[29, 41, 829, 2221], [3, 4]]
      [[33181, 66361], [3, 4]]

      all with false witnesses L = 3 and L = 4.
      I found these in a few seconds, by the obvious google.

      4) Finally, the promised Pinch, using,
      http://www.chalcedon.demon.co.uk/rgep/p20.pdf
      which reveals that Bill's algorithm cannot decide on the
      status of N = 443372888629441, even if we allow him
      to spend 200,000 selfridges:

      fail=0;all=0;N=443372888629441;A=bin(N);
      for(L=3,10^5+2,all++;t=lucas(N,A,L);if(t[1],fail++));
      print(fail"/"all" failures to decide");

      100000/100000 failures to decide

      David
    • djbroadhurst
      ... Ah, I see that I forgot the third coffin-nail. Here it is: 3) If Bill retorts by arbitrarily requiring 3 or 4 Lucas tests, I have more pseudoprimnes, in
      Message 2 of 4 , Oct 20, 2010
      View Source
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "djbroadhurst" <d.broadhurst@...> wrote:

        > 1) My code is modelled on Bill's and hence is very inefficient.
        > It is notable that Bill requires 55 Lucas tests to conclude
        > that 1412759 is probably prime

        > 2) It is easy to find larger pseudoprimes.
        > Here are 5 greater than 2*10^9:
        > fooled=[2023351681,2050864921,2099611801,2189197501,2201924341]

        > 4) Finally, the promised Pinch, using,
        > http://www.chalcedon.demon.co.uk/rgep/p20.pdf
        > which reveals that Bill's algorithm cannot decide on the
        > status of N = 443372888629441, even if we allow him
        > to spend 200,000 selfridges

        Ah, I see that I forgot the third coffin-nail. Here it is:

        3) If Bill retorts by arbitrarily requiring 3 or 4 Lucas tests,
        I have more pseudoprimnes, in waiting, with which to reply.
        In any case, he is doomed, by the absolute Pinch, as given in (4).

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