This site is supported by donations to The OEIS Foundation.
User:Karsten Meyer/strong pseudoprimes source
Program to find strong pseudoprimes (in REXX):
/* Ein REXX-Programm */ call load 'mod_up.r' zl.2 = 1 zl.4 = 2 zl.8 = 3 zl.16 = 4 zl.32 = 5 zl.64 = 6 zl.128 = 7 zl.256 = 8 zl.512 = 9 zl.1024 = 10 zl.2048 = 11 zl.4096 = 12 zl.8192 = 13 zl.16384 = 14 zl.32768 = 15 /* */ zp.0 = 1 zp.1 = 2 zp.2 = 4 zp.3 = 8 zp.4 = 16 zp.5 = 32 zp.6 = 64 zp.7 = 128 zp.8 = 256 zp.9 = 512 zp.10 = 1024 zp.11 = 2048 zp.12 = 4096 zp.13 = 8192 zp.14 = 16384 zp.15 = 32768 /* */ fpspr.1 = 15 fpspr.2 = 21 fpspr.3 = 25 fpspr.4 = 28 fpspr.5 = 33 fpspr.6 = 35 fpspr.7 = 39 fpspr.8 = 45 fpspr.9 = 49 fpspr.10 = 51 fpspr.11 = 52 fpspr.12 = 55 fpspr.13 = 57 fpspr.14 = 63 fpspr.15 = 65 fpspr.16 = 66 fpspr.17 = 69 fpspr.18 = 70 fpspr.19 = 75 fpspr.20 = 76 . . . fpspr.5933 = 11545 fpspr.5934 = 11546 fpspr.5935 = 11547 fpspr.5936 = 11548 fpspr.5937 = 11553 fpspr.5938 = 11554 fpspr.5939 = 11555 fpspr.5940 = 11557 fpspr.5941 = 11559 fpspr.5942 = 11561 fpspr.5943 = 11563 fpspr.5944 = 11565 fpspr.5945 = 11567 fpspr.5946 = 11569 fpspr.5947 = 11571 fpspr.5948 = 11573 fpspr.5949 = 11575 fpspr.5950 = 11577 fpspr.5951 = 11578 fpspr.5952 = 11581 fpspr.5953 = 11583 fpspr.5954 = 11584 fpspr.5955 = 11585 fpspr.5956 = 11586 fpspr.5957 = 11589 fpspr.5958 = 11590 fpspr.5959 = 11591 fpspr.5960 = 11595 fpspr.5961 = 11596 fpspr.5962 = 11599 fpspr.5963 = 11600 fpspr.5964 = 11601 fpspr.5965 = 11603 fpspr.5966 = 11605 fpspr.5967 = 11607 fpspr.5968 = 11609 fpspr.5969 = 11611 fpspr.5970 = 11613 fpspr.5971 = 11615 fpspr.5972 = 11616 fpspr.5973 = 11619 fpspr.5974 = 11620 fpspr.5975 = 11623 fpspr.5976 = 11625 fpspr.5977 = 11627 fpspr.5978 = 11629 anzfpspr = 5978 do i=1 to anzfpspr if ((fpspr.i // 2) = 1) then do say fpspr.i d = (fpspr.i - 1) do forever d = d % 2 if ((d // 2) = 1) then leave end t2 = (fpspr.i - 1) % d say fpspr.i d t2 do i2 = 0 to zl.t2 /* say d*i2 */ do i3 = 2 to (fpspr.i - 2) /* say i3 */ call m_u i3, d*zp.i2, fpspr.i pt = result t3 = (pt-1)*(pt-(fpspr.i-1)) if (t3 = 0) then do lineout("spspr_table1.txt", fpspr.i||", "||d||", "||d*zp.i2||", "||i3||", "||pt) end t3 = (pt-i3)*(pt-(fpspr.i-i3)) if (t3 = 0) then do lineout("spspr_table2.txt", fpspr.i||", "||d||", "||d*zp.i2||", "||i3||", "||pt) end end end end end pull x
The heart of the Program (and fermat pseudoprimes, euler pseudoprimes) is:
/* REXX-Programm */ say 'Only a Library!' exit 1 /* */ /* */ m_u: procedure arg a,l,m /* initialisierung */ as = a ai = a li = (l-1) DO li a = a * ai a = a // m END return a
The program will generate a list of this form:
15, 7, 14, 4, 1 15, 7, 14, 11, 1 21, 5, 10, 8, 1 21, 5, 10, 13, 1 21, 5, 20, 8, 1 21, 5, 20, 13, 1 25, 3, 6, 7, 24 25, 3, 6, 18, 24 25, 3, 12, 7, 1 25, 3, 12, 18, 1 25, 3, 24, 7, 1 25, 3, 24, 18, 1 33, 1, 2, 10, 1 33, 1, 2, 23, 1 33, 1, 4, 10, 1 33, 1, 4, 23, 1 33, 1, 8, 10, 1 33, 1, 8, 23, 1 33, 1, 16, 10, 1 33, 1, 16, 23, 1 33, 1, 32, 10, 1 33, 1, 32, 23, 1 35, 17, 34, 6, 1 35, 17, 34, 29, 1 39, 19, 38, 14, 1 39, 19, 38, 25, 1 45, 11, 22, 19, 1 45, 11, 22, 26, 1 45, 11, 44, 8, 1 45, 11, 44, 17, 1 45, 11, 44, 19, 1 45, 11, 44, 26, 1 45, 11, 44, 28, 1 45, 11, 44, 37, 1 49, 3, 3, 18, 1 49, 3, 3, 19, 48 49, 3, 3, 30, 1 49, 3, 3, 31, 48 49, 3, 6, 18, 1 49, 3, 6, 19, 1 49, 3, 6, 30, 1 49, 3, 6, 31, 1 49, 3, 12, 18, 1 49, 3, 12, 19, 1 49, 3, 12, 30, 1 49, 3, 12, 31, 1 49, 3, 24, 18, 1 49, 3, 24, 19, 1 49, 3, 24, 30, 1 49, 3, 24, 31, 1 49, 3, 48, 18, 1 49, 3, 48, 19, 1 49, 3, 48, 30, 1 49, 3, 48, 31, 1 51, 25, 50, 16, 1 51, 25, 50, 35, 1 55, 27, 54, 21, 1 55, 27, 54, 34, 1 57, 7, 14, 20, 1 57, 7, 14, 37, 1 57, 7, 28, 20, 1 57, 7, 28, 37, 1 57, 7, 56, 20, 1 57, 7, 56, 37, 1 63, 31, 62, 8, 1 63, 31, 62, 55, 1 65, 1, 2, 8, 64 65, 1, 2, 14, 1 65, 1, 2, 18, 64 65, 1, 2, 47, 64 65, 1, 2, 51, 1 65, 1, 2, 57, 64 65, 1, 4, 8, 1 65, 1, 4, 12, 1 65, 1, 4, 14, 1 65, 1, 4, 18, 1 65, 1, 4, 21, 1 65, 1, 4, 27, 1 65, 1, 4, 31, 1 65, 1, 4, 34, 1 65, 1, 4, 38, 1 65, 1, 4, 44, 1 65, 1, 4, 47, 1 65, 1, 4, 51, 1 65, 1, 4, 53, 1 65, 1, 4, 57, 1 65, 1, 8, 8, 1 65, 1, 8, 12, 1 65, 1, 8, 14, 1 65, 1, 8, 18, 1 65, 1, 8, 21, 1 65, 1, 8, 27, 1 65, 1, 8, 31, 1 65, 1, 8, 34, 1 65, 1, 8, 38, 1 65, 1, 8, 44, 1 65, 1, 8, 47, 1 65, 1, 8, 51, 1 65, 1, 8, 53, 1 65, 1, 8, 57, 1 65, 1, 16, 8, 1 65, 1, 16, 12, 1 65, 1, 16, 14, 1 65, 1, 16, 18, 1 65, 1, 16, 21, 1 65, 1, 16, 27, 1 65, 1, 16, 31, 1 65, 1, 16, 34, 1 65, 1, 16, 38, 1 65, 1, 16, 44, 1 65, 1, 16, 47, 1 65, 1, 16, 51, 1 65, 1, 16, 53, 1 65, 1, 16, 57, 1 65, 1, 32, 8, 1 65, 1, 32, 12, 1 65, 1, 32, 14, 1 65, 1, 32, 18, 1 65, 1, 32, 21, 1 65, 1, 32, 27, 1 65, 1, 32, 31, 1 65, 1, 32, 34, 1 65, 1, 32, 38, 1 65, 1, 32, 44, 1 65, 1, 32, 47, 1 65, 1, 32, 51, 1 65, 1, 32, 53, 1 65, 1, 32, 57, 1 65, 1, 64, 8, 1 65, 1, 64, 12, 1 65, 1, 64, 14, 1 65, 1, 64, 18, 1 65, 1, 64, 21, 1 65, 1, 64, 27, 1 65, 1, 64, 31, 1 65, 1, 64, 34, 1 65, 1, 64, 38, 1 65, 1, 64, 44, 1 65, 1, 64, 47, 1 65, 1, 64, 51, 1 65, 1, 64, 53, 1 65, 1, 64, 57, 1 69, 17, 34, 22, 1 69, 17, 34, 47, 1 69, 17, 68, 22, 1 69, 17, 68, 47, 1 75, 37, 74, 26, 1 75, 37, 74, 49, 1 77, 19, 38, 34, 1 77, 19, 38, 43, 1 77, 19, 76, 34, 1 77, 19, 76, 43, 1 85, 21, 42, 13, 84 85, 21, 42, 16, 1 85, 21, 42, 38, 84 85, 21, 42, 47, 84 85, 21, 42, 69, 1 85, 21, 42, 72, 84 85, 21, 84, 4, 1 85, 21, 84, 13, 1 85, 21, 84, 16, 1 85, 21, 84, 18, 1 85, 21, 84, 21, 1 85, 21, 84, 33, 1 85, 21, 84, 38, 1 85, 21, 84, 47, 1 85, 21, 84, 52, 1 85, 21, 84, 64, 1 85, 21, 84, 67, 1 85, 21, 84, 69, 1 85, 21, 84, 72, 1 85, 21, 84, 81, 1 87, 43, 86, 28, 1 87, 43, 86, 59, 1 91, 45, 45, 9, 1 91, 45, 45, 10, 90 91, 45, 45, 12, 90 91, 45, 45, 16, 1 91, 45, 45, 17, 90 91, 45, 45, 22, 1 91, 45, 45, 29, 1 91, 45, 45, 38, 90 91, 45, 45, 53, 1 91, 45, 45, 62, 90 91, 45, 45, 69, 90 91, 45, 45, 74, 1 91, 45, 45, 75, 90 91, 45, 45, 79, 1 91, 45, 45, 81, 1 91, 45, 45, 82, 90 91, 45, 90, 3, 1 91, 45, 90, 4, 1 91, 45, 90, 9, 1 91, 45, 90, 10, 1 91, 45, 90, 12, 1 91, 45, 90, 16, 1 91, 45, 90, 17, 1 91, 45, 90, 22, 1 91, 45, 90, 23, 1 91, 45, 90, 25, 1 91, 45, 90, 27, 1 91, 45, 90, 29, 1 91, 45, 90, 30, 1 91, 45, 90, 36, 1 91, 45, 90, 38, 1 91, 45, 90, 40, 1 91, 45, 90, 43, 1 91, 45, 90, 48, 1 91, 45, 90, 51, 1 91, 45, 90, 53, 1 91, 45, 90, 55, 1 91, 45, 90, 61, 1 91, 45, 90, 62, 1 91, 45, 90, 64, 1 91, 45, 90, 66, 1 91, 45, 90, 68, 1 91, 45, 90, 69, 1 91, 45, 90, 74, 1 91, 45, 90, 75, 1 91, 45, 90, 79, 1 91, 45, 90, 81, 1 91, 45, 90, 82, 1 91, 45, 90, 87, 1 91, 45, 90, 88, 1 93, 23, 46, 32, 1 93, 23, 46, 61, 1 93, 23, 92, 32, 1 93, 23, 92, 61, 1 95, 47, 94, 39, 1 95, 47, 94, 56, 1 99, 49, 98, 10, 1 99, 49, 98, 89, 1 . . .
The rest is done be hand (brain)
49:
49, 3, 3, 18, 1 49, 3, 3, 19, 48 49, 3, 3, 30, 1 49, 3, 3, 31, 48
49 is a strong pseudoprime to the bases 18, 19, 30 and 31 with d=3
325:
325, 81, 81, 49, 324 325, 81, 81, 126, 1 325, 81, 81, 199, 324 325, 81, 81, 276, 1 325, 81, 162, 7, 324 325, 81, 162, 18, 324 325, 81, 162, 32, 324 325, 81, 162, 57, 324 325, 81, 162, 93, 324 325, 81, 162, 132, 324 325, 81, 162, 193, 324 325, 81, 162, 232, 324 325, 81, 162, 268, 324 325, 81, 162, 293, 324 325, 81, 162, 307, 324 325, 81, 162, 318, 324
325 is a strong pseudoprime to the bases 49, 126, 199, 276, 7, 18, 32, 57, 93, 132, 193, 232, 268, 293, 307, 318