(50g) Fibonnaci Pseudoprime Test & Prime Test
02-17-2019, 05:47 PM (This post was last modified: 02-18-2019 06:13 AM by Gerald H.)
Post: #1
 Gerald H Senior Member Posts: 1,438 Joined: May 2014
(50g) Fibonnaci Pseudoprime Test & Prime Test
Edited as per next posting 2019-02-18.

Designating the members of Fibonnaci sequence

0,1,1,2,3,5......

as

f(0), f(1), f(2), f(3), f(4), f(5).......

and setting for integer N

g(N) := 1 if N = +/-1 mod 5
g(N) := -1 if N = +/-2 mod 5
g(N) := 0 if N = 0 mod 5

then if integer N is prime

f(N - g(N)) = 0 mod N.

The programme below runs the above test speedily.

Caveat: Some composite numbers, Fibonnaci pseudoprimes, pass the test, the programme erroneously returning 1, indicating primality, rather than 0.

However no number of the form

N = +/-2 mod 5

which passes the above test & is a base 2 pseudoprime has been shown to be composite (as of 2019-02-17, ref Crandall & Pomerance, Prime Numbers).

Size: 320.

CkSum: # ECD0h

Code:
::   CK1&Dispatch   # FF   ::     ::       FPTR2 ^ZABS       FPTR2 ^DupZIsTwo?       casedrptru       FPTR2 ^DupZIsEven?       casedrpfls       DUP       ZINT 5       Z=       casedrptru       DUP       ZINT 5       FPTR2 ^QMod       FPTR2 ^ZABS       FPTR2 ^DupQIsZero?       case2drpfls       FPTR2 ^ZIsOne?       ITE       ZINT -1       ZINT 1       OVER       FPTR2 ^QAdd       SWAP       ::         SWAPDUP         ZINT 2         Z<         case         SWAPDROP         FPTR2 ^Z>ZH         ZINT -2         ZINT 0         ZINT 1         4PICK         FPTR2 ^ZBits         SWAPDROP#1-_         ZERO_DO         FPTR2 ^ZSQ_         5PICK         FPTR2 ^ZMod         SWAP         FPTR2 ^ZSQ_         5PICK         FPTR2 ^ZMod         2DUP         FPTR2 ^RSUBext         DUP         FPTR2 ^RADDext         3PICK         FPTR2 ^RADDext         3UNROLL         FPTR2 ^RADDext         SWAPROT         FPTR2 ^RADDext         3PICK         ISTOP-INDEX         #1-         FPTR2 ^ZBit?         SWAPDROP         ITE         ::           DUPUNROT           FPTR2 ^QAdd           ZINT -2         ;         ZINT 2         3UNROLL         LOOP         4UNROLL3DROP         SWAP         FPTR2 ^Mod       ;       FPTR2 ^QIsZero?     ;     COERCEFLAG   ; ;
 « Next Oldest | Next Newest »

 Messages In This Thread (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-17-2019 05:47 PM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-17-2019, 09:12 PM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-18-2019, 03:01 AM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-18-2019, 06:18 AM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-26-2019, 07:55 AM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-26-2019, 02:03 PM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-26-2019, 04:29 PM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-26-2019, 06:18 PM RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-26-2019, 06:30 PM

User(s) browsing this thread: 1 Guest(s)