- dear kraDen,

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

successful. Here's the final corrections for T-Sequence; if it

works, then it works... if it doesn't, then it will always fail.

the array size for A() might have to increase for larger N's.

this is the absolute final last ditch effort; note: Line 146 steps

by ones.

thanks to all that have tested it! still hoping it'll work...

I don't have a big integer package, or the internet at home even.

Bill

100 CLS : C = 1

102 DIM A(1001), T(3)

104 FOR N = 3 TO 7919 STEP 2

106 IF (N <> 3 AND N MOD 3 <> 0) AND (N <> 5 AND N MOD 5 <> 0) THEN

108 A(0) = N: A(1) = (N + 1) / 2: A(2) = A(1) - 1

110 FOR I = 3 TO 1001 STEP 2

112 IF A(I - 1) <= 2 THEN

114 IF A(I - 1) = 2 THEN

116 A(I) = 1: A(I + 1) = 0

118 M = I + 1: I = 1001

120 ELSE

122 A(I) = 0: M = I: I = 1001

124 END IF

126 ELSE

128 IF A(I - 1) MOD 2 = 1 THEN

130 A(I) = A(I - 2) / 2

132 ELSE

134 A(I) = (A(I - 2) + 1) / 2

136 END IF

138 A(I + 1) = A(I) - 1

140 END IF

142 NEXT I

144 P = 0

146 FOR L = 3 TO N - 2

I know that I told you to step by two's in this loop; ignore that

148 T(0) = 2: T(1) = L: T(2) = (T(1) ^ 2 - 2) MOD N

150 IF T(2) <= 1 THEN T(2) = T(2) + N

152 K = 0: FLAG = 0: Z1 = 0: Z2 = 0

154 FOR J = M - 3 TO 0 STEP -1

156 IF A(J) MOD 2 = 1 THEN

158 IF A(J) = A(J + 1) + A(J + 2) THEN K = 0 ELSE K = 1

160 T(3) = (T(2 - K) * T(1 - K) - L) MOD N

162 ELSE

164 T(3) = (T(1) ^ 2 - 2) MOD N

166 END IF

168 IF T(3) <= 1 THEN T(3) = T(3) + N

170 IF T(3) = 2 AND J <> 1 THEN

172 J = 0: FLAG = 1: REM period must be full for valid test

174 ELSE

176 IF J = 2 THEN

178 Z1 = (T(3) ^ 2 - 2) MOD N

180 IF Z1 <= 1 THEN Z1 = Z1 + N

182 END IF

184 IF J = 1 THEN

186 Z2 = (T(3) ^ 2 - 2) MOD N

188 IF Z2 <= 1 THEN Z2 = Z2 + N

190 END IF

192 T(0) = T(1): T(1) = T(2): T(2) = T(3)

194 END IF

196 NEXT J

198 IF FLAG <> 1 THEN

200 Q = (L ^ 2 - 2) MOD N

202 IF Q <= 1 THEN Q = Q + N

204 IF T(3) = L THEN

206 IF (Z1 = 2 AND Z2 = Q) OR (Z1 = Q AND Z2 = 2) THEN

208 FLAG = 0: P = P + 1

210 ELSE

212 PRINT N; "is composite!": L = N - 2

214 END IF

216 ELSE

218 PRINT N; "is composite!": L = N - 2

220 END IF

222 END IF

224 IF P = 2 THEN PRINT N; "is prime!,"; P: L = N - 2: C = C + 1

225 REM SLEEP 3

226 NEXT L

230 ELSE

232 IF N = 3 OR N = 5 THEN

234 PRINT N; "is prime!": C = C + 1

236 ELSE

238 PRINT N; "is composite!"

240 END IF

242 END IF

244 NEXT N

246 PRINT C

248 END

cheers, as you'd say! - David, kraDen,

I'm elaborating on the post, previous to this one:

the 2 problems that plagued the programs before this one were...

L ranges from 3 to (something larger than 25) up to N -2, but it

will never reach such a large value,

and the size of array A will grow slightly as N grows in size.

those two considerations should be the final corrections.

there is nothing else to correct; there wouldn't be any other

version than the one just posted...

Bill - --- 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 - --- 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