faster than the APR algorithm

Expand Messages
• I believe that this algorithm proves primality faster than the APR algorithm, not compositeness, but primality; if both this T-sequence algorithm and the APR
Message 1 of 33 , May 21, 2010
I believe that this algorithm proves primality faster than the
APR algorithm, not compositeness, but primality; if both this
T-sequence algorithm and the APR algorithm were written in the
same language and had the same FFT's and CPU available, then I
believe the T-sequence would beat it; assuming that variables
were computed on the fly... i.e. no stored values allowed.

10 CLS : C = 1
12 DIM A(100), S(3), T(3)
14 OPEN "C:\heinz57.txt" FOR OUTPUT AS #1
15 REM it doesn't work for N = 231 where the curves cross
16 FOR N = 3 TO 7919 STEP 2
18 IF N <> 231 THEN
20 A(0) = N: A(1) = (N + 1) / 2: A(2) = A(1) - 1
22 FOR J = 3 TO 100 STEP 2
24 IF A(J - 1) <= 2 THEN
26 IF A(J - 1) = 2 THEN
28 A(J) = 1: A(J + 1) = 0: M = J + 1: J = 100
30 ELSE
32 A(J) = 0: M = J: J = 100
34 END IF
36 ELSE
38 IF A(J - 1) MOD 2 = 1 THEN
40 A(J) = A(J - 2) / 2
42 ELSE
44 A(J) = (A(J - 2) + 1) / 2
46 END IF
48 A(J + 1) = A(J) - 1
50 END IF
52 NEXT J
54 S(0) = 2: S(1) = 4: S(2) = (S(1) ^ 2 - 2) MOD N
56 T(0) = 2: T(1) = 3: T(2) = (T(1) ^ 2 - 2) MOD N
58 IF T(2) = 0 THEN T(2) = T(2) + N
60 IF S(2) = 0 THEN S(2) = S(2) + N
62 K = 0
64 FOR L = M - 3 TO 0 STEP -1
66 IF A(L) MOD 2 = 1 THEN
68 IF A(L) = A(L + 1) + A(L + 2) THEN K = 0 ELSE K = 1
70 S(3) = (S(2 - K) * S(1 - K) - 4) MOD N
72 T(3) = (T(2 - K) * T(1 - K) - 3) MOD N
74 ELSE
76 S(3) = (S(1) ^ 2 - 2) MOD N
78 T(3) = (T(1) ^ 2 - 2) MOD N
80 END IF
82 IF S(3) <= 1 THEN S(3) = S(3) + N
84 IF T(3) <= 1 THEN T(3) = T(3) + N
85 IF L = 0 AND T(3) = 3 AND S(3) = 4 THEN PRINT #1, A(L);: C = C + 1
86 IF L = 0 AND C MOD 10 = 0 AND T(3) = 3 AND S(3) = 4 THEN PRINT #1, ""
88 S(0) = S(1): S(1) = S(2): S(2) = S(3)
90 T(0) = T(1): T(1) = T(2): T(2) = T(3)
92 NEXT L
94 END IF
96 NEXT N
98 CLOSE #1

Bill, hoping that someone would comment on it other than DjBrst
• ... You did very much what I did. I nearly fell off the chair when I averaged everything out and saw 0.57... :-) ... Not very. Would you buy an appeal to
Message 33 of 33 , May 27, 2010
>
> I tried 1/n^c:
>
> v=[1237.1, 328.7, 105.4, 28.01, 6.22 , 1.510, 0.439, 0.0939];
> print(vector(8,k,-log(v[k]/10^6)/(k+4)/log(10)));
>
> [0.5815, 0.5805, 0.5682, 0.5691, 0.5785, 0.5821, 0.5780, 0.5856]
>
> and then A/n^c, using the first datum to remove A:
>
> print(vector(7,k,-log(v[k+1]/v[1])/k/log(10)));
>
> [0.5756, 0.5348, 0.5484, 0.5747, 0.5827, 0.5750, 0.5885]
>
> In both cases c =~ Euler looks rather convincing,
> given the statistics. Well spotted, Sir!

You did very much what I did.
I nearly fell off the chair when I averaged everything out and saw 0.57... :-)

> How strongly are you committed to A = 1, for the average,
> given the variability of the overall factor with a?

Not very.
Would you buy an appeal to Occam's razor, mon vieux?

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