## final corrections for T-Sequence

Expand Messages
• 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
Message 1 of 4 , Oct 19, 2010

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
Message 2 of 4 , Oct 19, 2010
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
• ... 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 3 of 4 , Oct 19, 2010
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 4 of 4 , Oct 20, 2010

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