Zsigmondy numbers: Difference between revisions
Added Algol 68
m (→{{header|Wren}}: Minor tidy though [7, 3] no longer works for 20 terms with first version.) |
(Added Algol 68) |
||
Line 52:
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find some Zsigmondy numbers #
# integral mode that has precision to suit the task - adjust to suit #
MODE INTEGER = LONG INT;
# returns the square root of n, use the sqrt routine appropriate for #
# the INTEGER mode #
PROC isqrt = ( INTEGER n )INTEGER: ENTIER long sqrt( n );
# returns the gcd of m and n #
PRIO GCD = 1;
OP GCD = ( INTEGER m, n )INTEGER:
BEGIN
INTEGER a := ABS m, b := ABS n;
WHILE b /= 0 DO
INTEGER new a = b;
b := a MOD b;
a := new a
OD;
a
END # GCD # ;
# returns TRUE if all m are coprime to n, FALSE otherwise #
PRIO ALLCOPRIME = 1;
OP ALLCOPRIME = ( []INTEGER m, INTEGER n )BOOL:
BEGIN
BOOL coprime := TRUE;
INTEGER abs n = ABS n;
FOR i FROM LWB m TO UPB m WHILE coprime := ( m[ i ] GCD n ) = 1 DO SKIP OD;
coprime
END # ALLCOPRIME # ;
# returns the sequence of Zsigmondy numbers of n to a, b #
PROC zsigmondy = ( INT n, a, b )[]INTEGER:
BEGIN
[ 1 : n - 1 ]INTEGER am minus bm;
INTEGER am := 1, bm := 1;
FOR m TO n - 1 DO
am minus bm[ m ] := ( am *:= a ) - ( bm *:= b )
OD;
INTEGER an := 1, bn := 1;
[ 1 : n ]INTEGER z;
FOR i TO n DO
INTEGER an minus bn = ( an *:= a ) - ( bn *:= b );
INTEGER largest divisor := 1;
IF am minus bm[ 1 : i - 1 ] ALLCOPRIME an minus bn THEN
largest divisor := an minus bn
ELSE
INTEGER d := 1;
INTEGER max d := isqrt( an minus bn );
WHILE ( d +:= 1 ) <= max d DO
IF an minus bn MOD d = 0 THEN
# d is a divisor of a^n - b^n #
IF d > largest divisor THEN
IF am minus bm[ 1 : i - 1 ] ALLCOPRIME d THEN largest divisor := d FI
FI;
INTEGER other d = an minus bn OVER d;
IF other d > d AND other d > largest divisor THEN
IF am minus bm[ 1 : i - 1 ] ALLCOPRIME other d THEN largest divisor := other d FI
FI
FI
OD
FI;
z[ i ] := largest divisor
OD;
z
END # zsigmondy # ;
[,]INT tests = ( ( 2, 1 ), ( 3, 1 ), ( 4, 1 ), ( 5, 1 ), ( 6, 1 )
, ( 7, 1 ), ( 3, 2 ), ( 5, 3 ), ( 7, 3 ), ( 7, 5 )
);
FOR i FROM LWB tests TO UPB tests DO
INT a = tests[ i, 1 ], b = tests[ i, 2 ];
[]INTEGER z = zsigmondy( 20, a, b );
print( ( "zsigmondy( 20, ", whole( a, 0 ), ", ", whole( b, 0 ), " ):", newline, " " ) );
FOR z pos FROM LWB z TO UPB z DO print( ( " ", whole( z[ z pos ], 0 ) ) ) OD;
print( ( newline, newline ) )
OD
END
</syntaxhighlight>
{{out}}
<pre>
zsigmondy( 20, 2, 1 ):
1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19 524287 41
zsigmondy( 20, 3, 1 ):
2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703 581130733 1181
zsigmondy( 20, 4, 1 ):
3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033 91625968981 61681
zsigmondy( 20, 5, 1 ):
4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167 4768371582031 375601
zsigmondy( 20, 6, 1 ):
5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441 121871948002099 1634221
zsigmondy( 20, 7, 1 ):
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307 1899815864228857 1129901
zsigmondy( 20, 3, 2 ):
1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577 1161737179 4621
zsigmondy( 20, 5, 3 ):
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979 9536162033329 288961
zsigmondy( 20, 7, 3 ):
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117 2849723505777919 4871281
zsigmondy( 20, 7, 5 ):
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201
</pre>
=={{header|Amazing Hopper}}==
| |||