Rosetta Code

Zsigmondy numbers: Difference between revisions

Page Discussion

Zsigmondy numbers (view source)

Revision as of 14:29, 19 February 2024

19,552 bytes added ,  3 months ago
→‎{{header|ALGOL 68}}: Slight optimisation
No edit summary
(→‎{{header|ALGOL 68}}: Slight optimisation)
 
(25 intermediate revisions by 11 users not shown)
Line 1:
{{draft task}}
 
'''Zsigmondy numbers''' '''n''' to '''a''', '''b''', are the greatest divisor of '''a<sup>n</sup> - b<sup>n</sup>''' that is coprime to '''a<sup>m</sup> - b<sup>m</sup>''' for all positive integers '''m < n'''.
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 187 ⟶ 449:
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public final class ZsigmondyNumbers {
 
public static void main(String[] args) {
record Pair(int a, int b) {}
List<Pair> pairs = List.of( new Pair(2, 1), new Pair(3, 1), new Pair(4, 1), new Pair(5, 1),
new Pair(6, 1), new Pair(7, 1), new Pair(3, 2), new Pair(5, 3), new Pair(7, 3), new Pair(7, 5) );
for ( Pair pair : pairs ) {
System.out.println("Zsigmondy(n, " + pair.a + ", " + pair.b + ")");
for ( int n = 1; n <= 18; n++ ) {
System.out.print(zsigmondyNumber(n, pair.a, pair.b) + " ");
}
System.out.println(System.lineSeparator());
}
}
private static long zsigmondyNumber(int n, int a, int b) {
final long dn = (long) ( Math.pow(a, n) - Math.pow(b, n) );
if ( isPrime(dn) ) {
return dn;
}
List<Long> divisors = divisors(dn);
for ( int m = 1; m < n; m++ ) {
long dm = (long) ( Math.pow(a, m) - Math.pow(b, m) );
divisors.removeIf( d -> gcd(dm, d) > 1 );
}
return divisors.get(divisors.size() - 1);
}
private static List<Long> divisors(long number) {
List<Long> result = new ArrayList<Long>();
for ( long d = 1; d * d <= number; d++ ) {
if ( number % d == 0 ) {
result.add(d);
if ( d * d < number ) {
result.add(number / d);
}
}
}
Collections.sort(result);
return result;
}
private static boolean isPrime(long number) {
if ( number < 2 ) {
return false;
}
if ( number % 2 == 0 ) {
return number == 2;
}
if ( number % 3 == 0 ) {
return number == 3;
}
int delta = 2;
long k = 5;
while ( k * k <= number ) {
if ( number % k == 0 ) {
return false;
}
k += delta;
delta = 6 - delta;
}
return true;
}
private static long gcd(long a, long b) {
while ( b != 0 ) {
long temp = a; a = b; b = temp % b;
}
return a;
}
 
}
</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|jq}}==
Line 309 ⟶ 686:
dexpms = map(i -> a^i - b^i, 1:n-1)
dexpn = a^n - b^n
return maximum(reduce(vcat, filter(d -> all(k -> gcd(k, d) == 1, dexpms), divisors(dexpn))))
end
 
Line 341 ⟶ 718:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
 
The Function:
Task:
Return the Zsigmondy-number to a,b,n integer:
Program:
<syntaxhighlight lang="mathematica">
ClearAll[zsigmondy]
Attributes[zsigmondy] = Listable;
zsigmondy[a_Integer, b_Integer, 1] := a - b /; a >= b;
Line 360 ⟶ 738:
 
<syntaxhighlight lang="mathematica">
data2 = MapThread[
zsigmondy[a_Integer, b_Integer, n_Integer] := (
zsigmondy, {{2, 3, 4, 5, 6, 7, 3, 5, 7, 7}, {1, 1, 1, 1, 1, 1, 2,
Attributes[zsigmondy] = Listable;
3, 3, 5}, {Range[10], Range[10], Range[10], Range[10], Range[10],
zsigmondy[a_Integer, b_Integer, 1] := a - b /; a >= b;
Range[10], Range[10], Range[10], Range[10], Range[10]}}];
zsigmondy[a_Integer, b_Integer, n_Integer] := (
hatvanyok = a^Range[n] - b^Range[n];
kishatvany = a^Range[n - 1] - b^Range[n - 1];
biggestelement = Part[hatvanyok, n];
divisors = Divisors[biggestelement];
divisorpairs = Join @@ (Thread[{#, kishatvany}] & /@ divisors);
coprimepairs = Select[divisorpairs, CoprimeQ[#[[1]], #[[2]]] &];
firstelement = coprimepairs[[All, 1]];
revesedelements = ReverseSort[firstelement];
Commonest[revesedelements, 1]) /; a >= b
 
l1 = Table[zsigmondy[2, 1, k], {k, Range[10]}];
l2 = Table[zsigmondy[3, 1, k], {k, Range[10]}];
l3 = Table[zsigmondy[4, 1, k], {k, Range[10]}];
l4 = Table[zsigmondy[5, 1, k], {k, Range[10]}];
l5 = Table[zsigmondy[6, 1, k], {k, Range[10]}];
l6 = Table[zsigmondy[7, 1, k], {k, Range[10]}];
l7 = Table[zsigmondy[3, 2, k], {k, Range[10]}];
l8 = Table[zsigmondy[5, 3, k], {k, Range[10]}];
l9 = Table[zsigmondy[7, 3, k], {k, Range[10]}];
l10 = Table[zsigmondy[7, 5, k], {k, Range[10]}];
matrix = {{l1}, {l2}, {l3}, {l4}, {l5}, {l6}, {l7}, {l8}, {l9}, {l10}};
data1 = List["Zsigmondy:2,1,n", "Zsigmondy:3,1,n", "Zsigmondy:4,1,n",
"Zsigmondy:5,1,n", "Zsigmondy:6,1,n", "Zsigmondy:7,1,n",
"Zsigmondy:3,2,n", "Zsigmondy:5,3,n", "Zsigmondy:7,3,n",
"Zsigmondy:7,5,n"];
data2 = matrix;
 
Grid[Transpose@{data1, data2}~
Prepend~{"pair of numbers", "Zsigmondy numbers"},
Line 397 ⟶ 752:
output:
<syntaxhighlight lang="mathematica">
Grid[{{"pair of numbers", Zsigmondy numbers
 
"Zsigmondy numbers"}, {"Zsigmondy:2,1,n", {{{1}, {3}, {7}, {5}, \
Zsigmondy:2,1,n {1, {3}, {7}, {5}, {31}, {1}, {127}, {17}, {73}, {11}}}},
 
{"Zsigmondy:3,1,n", {{{2}, {1}, {13}, {5}, {121}, {7}, {1093}, \
Zsigmondy:3,1,n {2, {1}, {13}, {5}, {121}, {7}, {1093}, {41}, {757}, {61}}
{41}, {757}, {61}}}},
 
{"Zsigmondy:4,1,n", {{{3}, {5}, {7}, {17}, {341}, {13}, {5461}, \
Zsigmondy:4,1,n {3, {5}, {7}, {17}, {341}, {13}, {5461}, {257}, {1387}, {41}}
{257}, {1387}, {41}}}},
 
{"Zsigmondy:5,1,n", {{{4}, {3}, {31}, {13}, {781}, {7}, {19531}, \
Zsigmondy:5,1,n {4, {3}, {31}, {13}, {781}, {7}, {19531}, {313}, {15751}, {521}}
{313}, {15751}, {521}}}},
 
{"Zsigmondy:6,1,n", {{{5}, {7}, {43}, {37}, {311}, {31}, \
Zsigmondy:6,1,n {559875, {7}, {129743}, {4687337}, {1111311}, {31}, {55987}, {1297}, {46873}, {1111}}
 
{"Zsigmondy:7,1,n", {{{6}, {1}, {19}, {25}, {2801}, {43}, \
Zsigmondy:7,1,n {1372576, {1}, {120119}, {3933125}, {21012801}, {43}, {137257}, {1201}, {39331}, {2101}}
 
{"Zsigmondy:3,2,n", {{{1}, {5}, {19}, {13}, {211}, {7}, {2059}, \
Zsigmondy:3,2,n {1, {5}, {19}, {13}, {211}, {7}, {2059}, {97}, {1009}, {11}}
{97}, {1009}, {11}}}},
 
{"Zsigmondy:5,3,n", {{{2}, {1}, {49}, {17}, {1441}, {19}, \
Zsigmondy:5,3,n {379692, {1}, {35349}, {1972917}, {4211441}, {19}, {37969}, {353}, {19729}, {421}}
 
{"Zsigmondy:7,3,n", {{{4}, {5}, {79}, {29}, {4141}, {37}, \
Zsigmondy:7,3,n {2053394, {5}, {124179}, {12763929}, {3414141}, {37}, {205339}, {1241}, {127639}, {341}}
 
{"Zsigmondy:7,5,n", {{{2}, {3}, {109}, {37}, {6841}, {13}, \
Zsigmondy:7,5,n {3727092, {3}, {1513109}, {17614937}, {16616841}, {13}, {372709}, {1513}, {176149}, {1661}}
Dividers -> {All, {1 -> True, 2 -> True}},
ItemSize -> {Automatic, Automatic}]
</syntaxhighlight>
 
=={{header|Nim}}==
<syntaxhighlight lang="Nim">import std/[algorithm, math, strformat]
 
func isPrime(n: Natural): bool =
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var k = 5
var delta = 2
while k * k <= n:
if n mod k == 0: return false
inc k, delta
delta = 6 - delta
result = true
 
func divisors(n: Positive): seq[int] =
for d in 1..sqrt(n.toFloat).int:
if n mod d == 0:
result.add d
if n div d != d:
result.add n div d
result.sort()
 
func zs(n, a, b: Positive): int =
let dn = a^n - b^n
if dn.isPrime: return dn
var divs = dn.divisors
for m in 1..<n:
let dm = a^m - b^m
for i in countdown(divs.high, 1):
if gcd(dm, divs[i]) != 1:
divs.delete i
result = divs[^1]
 
const N = 15
for (a, b) in [(2, 1), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), (3, 2), (5, 3), (7, 3), (7, 5)]:
echo &"Zsigmondy(n, {a}, {b}) – First {N} terms:"
for n in 1..N:
stdout.write zs(n, a, b), ' '
echo '\n'
</syntaxhighlight>
 
{{out}}
<pre>Zsigmondy(n, 2, 1) – First 15 terms:
1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151
 
Zsigmondy(n, 3, 1) – First 15 terms:
2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561
 
Zsigmondy(n, 4, 1) – First 15 terms:
3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981
 
Zsigmondy(n, 5, 1) – First 15 terms:
4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121
 
Zsigmondy(n, 6, 1) – First 15 terms:
5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371
 
Zsigmondy(n, 7, 1) – First 15 terms:
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001
 
Zsigmondy(n, 3, 2) – First 15 terms:
1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571
 
Zsigmondy(n, 5, 3) – First 15 terms:
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001
 
Zsigmondy(n, 7, 3) – First 15 terms:
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081
 
Zsigmondy(n, 7, 5) – First 15 terms:
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 </pre>
 
=={{header|Perl}}==
Line 621 ⟶ 1,046:
A109349: Zsigmondy(n,7,5):
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">use itertools::{max, all};
use gcd::Gcd;
use divisors::get_divisors;
 
fn zsigmondy(a: u64, b: u64, n: u64) -> u64 {
assert!(a > b);
let dexpms: Vec<u64> = (1..(n as u32)).map(|i| a.pow(i) - b.pow(i)).collect();
let dexpn: u64 = a.pow(n as u32) - b.pow(n as u32);
let mut divisors = get_divisors(dexpn).to_vec(); // get_divisors(n) does not include 1 and n
divisors.append(&mut [1, dexpn].to_vec()); // so add those
let z = divisors.iter().filter(|d| all(dexpms.clone(), |k| Gcd::gcd(k, **d) == 1));
return *max(z).unwrap();
}
 
fn main() {
for (name, a, b) in [
("A064078: Zsigmondy(n,2,1)", 2, 1,),
("A064079: Zsigmondy(n,3,1)", 3, 1,),
("A064080: Zsigmondy(n,4,1)", 4, 1,),
("A064081: Zsigmondy(n,5,1)", 5, 1,),
("A064082: Zsigmondy(n,6,1)", 6, 1,),
("A064083: Zsigmondy(n,7,1)", 7, 1,),
("A109325: Zsigmondy(n,3,2)", 3, 2,),
("A109347: Zsigmondy(n,5,3)", 5, 3,),
("A109348: Zsigmondy(n,7,3)", 7, 3,),
("A109349: Zsigmondy(n,7,5)", 7, 5,),] {
println!("\n{name}:");
for n in 1..21 {
print!("{} ", zsigmondy(a, b, n));
}
}
}
</syntaxhighlight>{{out}}
<pre>
A064078: Zsigmondy(n,2,1):
1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19 524287 41
A064079: Zsigmondy(n,3,1):
2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703 581130733 1181
A064080: Zsigmondy(n,4,1):
3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033 91625968981 61681
A064081: Zsigmondy(n,5,1):
4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167 4768371582031 375601
A064082: Zsigmondy(n,6,1):
5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441 121871948002099 1634221
A064083: Zsigmondy(n,7,1):
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307 1899815864228857 1129901
A109325: Zsigmondy(n,3,2):
1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577 1161737179 4621
A109347: Zsigmondy(n,5,3):
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979 9536162033329 288961
A109348: Zsigmondy(n,7,3):
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117 2849723505777919 4871281
A109349: Zsigmondy(n,7,5):
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}}==
{{trans|Perl}}
<syntaxhighlight lang="ruby">func zsigmondy (a, b, c) {
 
var aexp = (0..c -> map {|k| a**k })
var bexp = (0..c -> map {|k| b**k })
 
var z = []
for n in (1 .. c) {
divisors(aexp[n] - bexp[n]).flip.each {|d|
1 ..^ n -> all {|k|
aexp[k] - bexp[k] -> is_coprime(d)
} && (z << d; break)
}
}
return z
}
 
for name,a,b in ([
'A064078: Zsigmondy(n,2,1)', 2,1,
'A064079: Zsigmondy(n,3,1)', 3,1,
'A064080: Zsigmondy(n,4,1)', 4,1,
'A064081: Zsigmondy(n,5,1)', 5,1,
'A064082: Zsigmondy(n,6,1)', 6,1,
'A064083: Zsigmondy(n,7,1)', 7,1,
'A109325: Zsigmondy(n,3,2)', 3,2,
'A109347: Zsigmondy(n,5,3)', 5,3,
'A109348: Zsigmondy(n,7,3)', 7,3,
'A109349: Zsigmondy(n,7,5)', 7,5,
].slices(3)) {
say ("\n#{name}:\n", zsigmondy(a, b, 20))
}</syntaxhighlight>
{{out}}
<pre>A064078: Zsigmondy(n,2,1):
[1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 2047, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41]
 
A064079: Zsigmondy(n,3,1):
[2, 1, 13, 5, 121, 7, 1093, 41, 757, 61, 88573, 73, 797161, 547, 4561, 3281, 64570081, 703, 581130733, 1181]
 
A064080: Zsigmondy(n,4,1):
[3, 5, 7, 17, 341, 13, 5461, 257, 1387, 41, 1398101, 241, 22369621, 3277, 49981, 65537, 5726623061, 4033, 91625968981, 61681]
 
A064081: Zsigmondy(n,5,1):
[4, 3, 31, 13, 781, 7, 19531, 313, 15751, 521, 12207031, 601, 305175781, 13021, 315121, 195313, 190734863281, 5167, 4768371582031, 375601]
 
A064082: Zsigmondy(n,6,1):
[5, 7, 43, 37, 311, 31, 55987, 1297, 46873, 1111, 72559411, 1261, 2612138803, 5713, 1406371, 1679617, 3385331888947, 46441, 121871948002099, 1634221]
 
A064083: Zsigmondy(n,7,1):
[6, 1, 19, 25, 2801, 43, 137257, 1201, 39331, 2101, 329554457, 2353, 16148168401, 102943, 4956001, 2882401, 38771752331201, 117307, 1899815864228857, 1129901]
 
A109325: Zsigmondy(n,3,2):
[1, 5, 19, 13, 211, 7, 2059, 97, 1009, 11, 175099, 61, 1586131, 463, 3571, 6817, 129009091, 577, 1161737179, 4621]
 
A109347: Zsigmondy(n,5,3):
[2, 1, 49, 17, 1441, 19, 37969, 353, 19729, 421, 24325489, 481, 609554401, 10039, 216001, 198593, 381405156481, 12979, 9536162033329, 288961]
 
A109348: Zsigmondy(n,7,3):
[4, 5, 79, 29, 4141, 37, 205339, 1241, 127639, 341, 494287399, 2041, 24221854021, 82573, 3628081, 2885681, 58157596211761, 109117, 2849723505777919, 4871281]
 
A109349: Zsigmondy(n,7,5):
[2, 3, 109, 37, 6841, 13, 372709, 1513, 176149, 1661, 964249309, 1801, 47834153641, 75139, 3162961, 3077713, 115933787267041, 30133, 5689910849522509, 3949201]</pre>
 
=={{header|Wren}}==
Line 626 ⟶ 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 678 ⟶ 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 688 ⟶ 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,038

edits

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