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

final corrections for T-Sequence

Expand Messages
  • Bill Bouris
    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
    • 0 Attachment
      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!
    • leavemsg1
      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
      • 0 Attachment
        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
      • djbroadhurst
        ... 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
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          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]]

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

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