Rosetta Code

Zsigmondy numbers: Difference between revisions

Page Discussion

Zsigmondy numbers (view source)

Revision as of 14:29, 19 February 2024

10,211 bytes added ,  3 months ago
→‎{{header|ALGOL 68}}: Slight optimisation
(New post.)
(→‎{{header|ALGOL 68}}: Slight optimisation)
 
(13 intermediate revisions by 5 users not shown)
Line 52:
 
 
 
=={{header|ALGOL 68}}==
64-bit integers are needed to show some of the "larger" a, b values, adjust the INTEGER mode and isqrt procedure accordingly, if necessary for your compiler/interpreter.
<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 AND largest divisor <= 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 style="font-size: smaller;">
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}}==
<syntaxhighlight lang="c">
#include <basico.h>
 
#proto zsigmondy(_X_,_Y_,_Z_)
 
#define TOPE 11
 
algoritmo
decimales '0'
matrices(a,b)
'2,3,4,5,6,7,3,5,7,7' enlistar en 'a'
'1,1,1,1,1,1,2,3,3,5' enlistar en 'b'
imprimir( "Zsigmondy Numbers\n\n")
iterar para ( k=1, #(k<=10), ++k)
imprimir ("[11,",#(a[k]),",",#(b[k]),"] {")
iterar para( i=1, #(i<=TOPE), ++i )
imprimir( _zsigmondy(i, #(a[k]), #(b[k])),\
solo si ( #(i<TOPE), ","))
siguiente
"}\n", imprimir
siguiente
terminar
 
subrutinas
 
zsigmondy(i,a,b)
dn=0
si ' #( dn :=( a^i - b^i ) ), es primo? '
tomar 'dn'
sino
divisores=0
guardar 'divisores de (dn)' en 'divisores'
iterar para( m=1, #(m<i), ++m )
remover según( #(gcd((a^m-b^m),divisores )>1),\
divisores)
siguiente
tomar 'último elemento de (divisores)'
fin si
retornar
</syntaxhighlight>
 
{{out}}
<pre>
Zsigmondy Numbers
 
[11,2,1] {1,3,7,5,31,1,127,17,73,11,2047}
[11,3,1] {2,1,13,5,121,7,1093,41,757,61,88573}
[11,4,1] {3,5,7,17,341,13,5461,257,1387,41,1398101}
[11,5,1] {4,3,31,13,781,7,19531,313,15751,521,12207031}
[11,6,1] {5,7,43,37,311,31,55987,1297,46873,1111,72559411}
[11,7,1] {6,1,19,25,2801,43,137257,1201,39331,2101,329554457}
[11,3,2] {1,5,19,13,211,7,2059,97,1009,11,175099}
[11,5,3] {2,1,49,17,1441,19,37969,353,19729,421,24325489}
[11,7,3] {4,5,79,29,4141,37,205339,1241,127639,341,494287399}
[11,7,5] {2,3,109,37,6841,13,372709,1513,176149,1661,964249309}
 
</pre>
 
=={{header|C++}}==
Line 158 ⟶ 335:
 
</pre>
 
=={{header|EasyLang}}==
{{trans|Phix}}
<syntaxhighlight>
func isprim num .
if num < 2
return 0
.
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
proc sort . d[] .
for i = 1 to len d[] - 1
for j = i + 1 to len d[]
if d[j] < d[i]
swap d[j] d[i]
.
.
.
.
proc divisors num . res[] .
res[] = [ ]
d = 1
while d <= sqrt num
if num mod d = 0
res[] &= d
if d <> sqrt num
res[] &= num / d
.
.
d += 1
.
sort res[]
.
func gcd a b .
while b <> 0
h = b
b = a mod b
a = h
.
return a
.
func zsigmo n a b .
dn = pow a n - pow b n
if isprim dn = 1
return dn
.
divisors dn divs[]
for m = 1 to n - 1
dms[] &= pow a m - pow b m
.
for i = len divs[] downto 1
d = divs[i]
for m = 1 to n - 1
if gcd dms[m] d <> 1
break 1
.
.
if m = n
return d
.
.
return 1
.
proc test . .
test[][] = [ [ 2 1 ] [ 3 1 ] [ 4 1 ] [ 5 1 ] [ 6 1 ] [ 7 1 ] [ 3 2 ] [ 5 3 ] [ 7 3 ] [ 7 5 ] ]
for i to len test[][]
a = test[i][1]
b = test[i][2]
write "Zsigmondy(n, " & a & ", " & b & "):"
for n = 1 to 10
write " " & zsigmo n a b
.
print ""
.
.
test
</syntaxhighlight>
 
 
=={{header|J}}==
Line 841 ⟶ 1,103:
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201
</pre>
 
=={{header|SETL}}==
{{trans|Java}}
<syntaxhighlight lang="setl">program zsigmondy;
pairs := [[2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1],
[3, 2], [5, 3], [7, 3], [7, 5]];
 
loop for [a, b] in pairs do
print("Zsigmondy(n, " + str a + ", " + str b + ")");
loop for n in [1..18] do
putchar(str zs(n, a, b) + " ");
end loop;
print;
end loop;
 
proc zs(n,a,b);
dn := a**n - b**n;
divs := divisors(dn);
if #divs = 1 then return dn; end if;
 
loop for m in [1..n-1] do
dm := a**m - b**m;
divs -:= {d : d in divs | gcd(dm, d) > 1};
end loop;
return max/divs;
end proc;
 
proc divisors(n);
ds := {d : d in {1..floor(sqrt(n))} | n mod d=0};
return ds + {n div d : d in ds};
end proc;
 
proc gcd(a,b);
loop while b/=0 do
[a, b] := [b, a mod b];
end loop;
return a;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>Zsigmondy(n, 2, 1)
1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19
Zsigmondy(n, 3, 1)
2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703
Zsigmondy(n, 4, 1)
3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033
Zsigmondy(n, 5, 1)
4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167
Zsigmondy(n, 6, 1)
5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441
Zsigmondy(n, 7, 1)
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307
Zsigmondy(n, 3, 2)
1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577
Zsigmondy(n, 5, 3)
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979
Zsigmondy(n, 7, 3)
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117
Zsigmondy(n, 7, 5)
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133</pre>
 
=={{header|Sidef}}==
Line 909 ⟶ 1,231:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
Shows the first 20 terms for each radix set apart from [7, 1], [7, 3] and [7, 5] where I've had to limit the number of terms to 18 for now. This is because the 19th term is being calculated incorrectly due to 7^19 exceeding Wren's safe integer limit of 2^53. It's only by good fortune that [7, 3] works correctly.
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./fmt" for Fmt
 
Line 961 ⟶ 1,283:
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979 9536162033329 288961
 
Zsigmony(n, 7, 3) - first 2018 terms:
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117 2849723505777919 4871281
 
Zsigmony(n, 7, 5) - first 18 terms:
Line 971 ⟶ 1,293:
{{libheader|Wren-seq}}
However, we can deal with integers of any size by switching to BigInt.
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt
import "./big" for BigInt
import "./seq" for Lst
import "./fmt" for Fmt
Tigerofdarkness
3,044

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/358129...358143"