Loading ...
Sorry, an error occurred while loading the content.

faster than the APR algorithm

Expand Messages
  • leavemsg1
    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
    • 0 Attachment
      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
    • mikeoakes2
      ... 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
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
        >
        > 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.