This site is supported by donations to The OEIS Foundation.
User:Karsten Meyer/strong pseudoprimes source
From OeisWiki
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
