- View Source--- In primenumbers@yahoogroups.com,

Bill Bouris <leavemsg1@...> wrote:

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

Ken has already told you that there are 5 pseudoprimes

> successful

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 - View Source--- In primenumbers@yahoogroups.com,

"djbroadhurst" <d.broadhurst@...> wrote:

> 1) My code is modelled on Bill's and hence is very inefficient.

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

> 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

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