Browse Groups

• ## Re: final corrections for T-Sequence

(4)
• NextPrevious
• ... 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
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]]

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
• ... 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 1 of 4 , Oct 20, 2010
View Source

> 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.
• 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.