Carmichael 3 strong pseudoprimes: Difference between revisions
→{{header|EchoLisp}}: Add Fortran.
(→{{header|EchoLisp}}: Add Fortran.) |
|||
Line 376:
💥 824389441 = 61 x 3361 x 4021
</lang>
=={{header|Fortran}}==
This is F77 style, and directly translates the given calculation. It turns out that the normal integers suffice for the demonstration, except for just one of the products of the three primes: 41x1721x35281 = 2489462641, which is bigger than 2147483647, the 32-bit limit. Fortunately, INTEGER*8 variables are also available, so the extension is easy. Otherwise, one would have to mess about with using two integers in a bignum style, one holding say the millions, and the second the number up to a million.
Directly translating the given formulae involves a trap. There is an expression ''-Prime1 squared mod h3'', and translating this to <code>MOD(-P1**2,H3)</code> may not work. The behaviour of the MOD function for negative numbers varies between language, compiler, and cpu. For positive numbers there is no confusion. However, in some cases one wants an affine shift as in day-of-the-week calculations from a daynumber, D: given MOD(D,7), one wants the same result with MOD(D - 7,7) or any other such shift and indeed, this happens with some versions of MOD. But not all, as Prof. Knuth remarks in his description of the calculation of the date for Easter. The MOD function can also work as follows:
<pre>
D -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
MOD(D,3) -1 0 -2 -1 0 -2 -1 0 1 2 0 1 2 0 1
MOD(3 + MOD(D,3),3) 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1
</pre>
Here I am supposing that ''(h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3'' is evaluated as ''{[(h3 + Prime1)*(Prime1 - 1) mod d] == 0} and {[-(Prime1 squared) mod h3] == d mod h3}'' which is to say it is ''[-(Prime1 squared)] mod h3'' not ''-[(Prime1 squared) mod h3]'' where the first case involves the MOD(negative number) while the second is -MOD(positive number) and the only way that result could match ''d mod h3'' is when both are zero.
Testing with the peculiar sign ignored via <code>.AND. (MOD(P1**2,H3) .EQ. MOD(D,H3))) THEN</code> gives limited results:
<pre>
Carmichael numbers that are the product of three primes:
P1 x P2 x P3 = C
3 11 17 561
5 29 73 10585
7 19 67 8911
13 61 397 314821
13 37 241 115921
19 43 409 334153
31 991 15361 471905281
37 109 2017 8134561
41 1721 35281 2489462641
43 631 13567 368113411
43 271 5827 67902031
43 127 2731 14913991
61 421 12841 329769721
61 181 5521 60957361</pre>
Which turns out to be when the two terms have remainders of one. <lang Fortran> LOGICAL FUNCTION ISPRIME(N) !Ad-hoc, since N is not going to be big...
INTEGER N !Despite this intimidating allowance of 32 bits...
INTEGER F !A possible factor.
ISPRIME = .FALSE. !Most numbers aren't prime.
DO F = 2,SQRT(DFLOAT(N)) !Wince...
IF (MOD(N,F).EQ.0) RETURN !Not even avoiding even numbers byond two.
END DO !Nice and brief, though.
ISPRIME = .TRUE. !No factor found.
END FUNCTION ISPRIME !So, done. Hopefully, not often.
PROGRAM CHASE
INTEGER P1,P2,P3 !The three primes to be tested.
INTEGER H3,D !Assistants.
INTEGER MSG !File unit number.
MSG = 6 !Standard output.
WRITE (MSG,1) !A heading would be good.
1 FORMAT ("Carmichael numbers that are the product of three primes:"
& /" P1 x P2 x P3 =",9X,"C")
DO P1 = 2,61 !Step through the specified range.
IF (ISPRIME(P1)) THEN !Selecting only the primes.
DO H3 = 2,P1 - 1 !For 1 < H3 < P1.
DO D = 1,H3 + P1 - 1 !For 0 < D < H3 + P1.
IF (MOD((H3 + P1)*(P1 - 1),D).EQ.0 !Filter.
& .AND. (MOD(H3 + MOD(-P1**2,H3),H3) .EQ. MOD(D,H3))) THEN !Beware MOD for negative numbers! MOD(-P1**2, may surprise...
P2 = 1 + (P1 - 1)*(H3 + P1)/D !Candidate for the second prime.
IF (ISPRIME(P2)) THEN !Is it prime?
P3 = 1 + P1*P2/H3 !Yes. Candidate for the third prime.
IF (ISPRIME(P3)) THEN !Is it prime?
IF (MOD(P2*P3,P1 - 1).EQ.1) THEN !Yes! Final test.
PPP = P1 !This converts to INTEGER*8.
PPP = PPP*P2*P3 !So the product is computed that way, without named conversion functions.
WRITE (MSG,2) P1,P2,P3, INT8(P1)*P2*P3 !Result!
2 FORMAT (3I6,I12)
END IF
END IF
END IF
END IF
END DO
END DO
END IF
END DO
END</lang>
Output:<pre>
Carmichael numbers that are the product of three primes:
P1 x P2 x P3 = C
3 11 17 561
5 29 73 10585
5 17 29 2465
5 13 17 1105
7 19 67 8911
7 31 73 15841
7 13 31 2821
7 23 41 6601
7 73 103 52633
7 13 19 1729
13 61 397 314821
13 37 241 115921
13 97 421 530881
13 37 97 46657
13 37 61 29341
17 41 233 162401
17 353 1201 7207201
19 43 409 334153
19 199 271 1024651
23 199 353 1615681
29 113 1093 3581761
29 197 953 5444489
31 991 15361 471905281
31 61 631 1193221
31 151 1171 5481451
31 61 271 512461
31 61 211 399001
31 271 601 5049001
31 181 331 1857241
37 109 2017 8134561
37 73 541 1461241
37 613 1621 36765901
37 73 181 488881
37 73 109 294409
41 1721 35281 2489462641
41 881 12041 434932961
41 101 461 1909001
41 241 761 7519441
41 241 521 5148001
41 73 137 410041
41 61 101 252601
43 631 13567 368113411
43 271 5827 67902031
43 127 2731 14913991
43 127 1093 5968873
43 211 757 6868261
43 631 1597 43331401
43 127 211 1152271
43 211 337 3057601
43 433 643 11972017
43 547 673 15829633
43 3361 3907 564651361
47 3359 6073 958762729
47 1151 1933 104569501
47 3727 5153 902645857
53 157 2081 17316001
53 79 599 2508013
53 157 521 4335241
59 1451 2089 178837201
61 421 12841 329769721
61 181 5521 60957361
61 1301 19841 1574601601
61 277 2113 35703361
61 181 1381 15247621
61 541 3001 99036001
61 661 2521 101649241
61 271 571 9439201
61 241 421 6189121
61 3361 4021 824389441
</pre>
=={{header|Haskell}}==
| |||