Rosetta Code

Zsigmondy numbers: Difference between revisions

Page Discussion

Zsigmondy numbers (view source)

Revision as of 14:29, 19 February 2024

28,949 bytes added ,  3 months ago
→‎{{header|ALGOL 68}}: Slight optimisation
(Added C++ solution)
(→‎{{header|ALGOL 68}}: Slight optimisation)
 
(30 intermediate revisions by 13 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}}==
''Adapted from [[#Wren|Wren]]''
{{works with|jq}}
'''Works with gojq, the Go implementation of jq, and with fq.'''
 
The integer arithmetic precision of the C implementation of jq
is limited, but is sufficient for the specific set of tasks defined in this entry.
 
'''Generic Functions'''
<syntaxhighlight lang=jq>
# Input: an integer
def isPrime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
else 5
| until( . <= 0;
if .*. > $n then -1
elif ($n % . == 0) then 0
else . + 2
| if ($n % . == 0) then 0
else . + 4
end
end)
| . == -1
end;
 
# divisors as an unsorted stream
def divisors:
if . == 1 then 1
else . as $n
| label $out
| range(1; $n) as $i
| ($i * $i) as $i2
| if $i2 > $n then break $out
else if $i2 == $n
then $i
elif ($n % $i) == 0
then $i, ($n/$i)
else empty
end
end
end;
 
def gcd(a; b):
# subfunction expects [a,b] as input
# i.e. a ~ .[0] and b ~ .[1]
def rgcd: if .[1] == 0 then .[0]
else [.[1], .[0] % .[1]] | rgcd
end;
[a,b] | rgcd;
 
# To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
</syntaxhighlight>
'''The Zsigmondy Function'''
<syntaxhighlight lang=jq>
# Input: $n
def zs($a; $b):
. as $n
| (($a|power($n)) - ($b|power($n))) as $dn
| if ($dn|isPrime) then $dn
else ([$dn|divisors]|sort) as $divs
| [range(1; $n) as $m | ($a|power($m)) - ($b|power($m))] as $dms
| first( range( $divs|length-1; 0 ; -1) as $i
| if (all($dms[]; gcd(.; $divs[$i]) == 1 )) then $divs[$i] else empty end)
// 1
end;
</syntaxhighlight>
'''The Task'''
<syntaxhighlight lang=jq>
def abs:
[ [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [3, 2], [5, 3], [7, 3], [7, 5] ];
 
abs[] as [$a, $b]
| (if ($a == 7 and $b != 3) then 18 else 20 end) as $lim
| "Zsigmony(\($a), \($b)) - first \($lim) terms:",
[range(1; $lim+1) | zs($a; $b)]
</syntaxhighlight>
'''Invocation''': gojq -nrcf zsigmondy-numbers.jq
{{output}}
<pre>
Zsigmony(2, 1) - first 20 terms:
[1,3,7,5,31,1,127,17,73,11,2047,13,8191,43,151,257,131071,19,524287,41]
Zsigmony(3, 1) - first 20 terms:
[2,1,13,5,121,7,1093,41,757,61,88573,73,797161,547,4561,3281,64570081,703,581130733,1181]
Zsigmony(4, 1) - first 20 terms:
[3,5,7,17,341,13,5461,257,1387,41,1398101,241,22369621,3277,49981,65537,5726623061,4033,91625968981,61681]
Zsigmony(5, 1) - first 20 terms:
[4,3,31,13,781,7,19531,313,15751,521,12207031,601,305175781,13021,315121,195313,190734863281,5167,4768371582031,375601]
Zsigmony(6, 1) - first 20 terms:
[5,7,43,37,311,31,55987,1297,46873,1111,72559411,1261,2612138803,5713,1406371,1679617,3385331888947,46441,121871948002099,1634221]
Zsigmony(7, 1) - first 18 terms:
[6,1,19,25,2801,43,137257,1201,39331,2101,329554457,2353,16148168401,102943,4956001,2882401,38771752331201,117307]
Zsigmony(3, 2) - first 20 terms:
[1,5,19,13,211,7,2059,97,1009,11,175099,61,1586131,463,3571,6817,129009091,577,1161737179,4621]
Zsigmony(5, 3) - first 20 terms:
[2,1,49,17,1441,19,37969,353,19729,421,24325489,481,609554401,10039,216001,198593,381405156481,12979,9536162033329,288961]
Zsigmony(7, 3) - first 20 terms:
[4,5,79,29,4141,37,205339,1241,127639,341,494287399,2041,24221854021,82573,3628081,2885681,58157596211761,109117,2849723505777919,4871281]
Zsigmony(7, 5) - first 18 terms:
[2,3,109,37,6841,13,372709,1513,176149,1661,964249309,1801,47834153641,75139,3162961,3077713,115933787267041,30133]
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">""" Rosetta code task: rosettacode.org/wiki/Zsigmondy_numbers """
Line 205 ⟶ 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 234 ⟶ 715:
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|Mathematica}}/{{header|Wolfram Language}}==
 
The Function:
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;
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
</syntaxhighlight>
 
<syntaxhighlight lang="mathematica">
data2 = MapThread[
zsigmondy, {{2, 3, 4, 5, 6, 7, 3, 5, 7, 7}, {1, 1, 1, 1, 1, 1, 2,
3, 3, 5}, {Range[10], Range[10], Range[10], Range[10], Range[10],
Range[10], Range[10], Range[10], Range[10], Range[10]}}];
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"];
Grid[Transpose@{data1, data2}~
Prepend~{"pair of numbers", "Zsigmondy numbers"},
Dividers -> {All, {1 -> True, 2 -> True}}]
</syntaxhighlight>
output:
<syntaxhighlight lang="mathematica">
pair of numbers Zsigmondy numbers
 
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}, {41}, {757}, {61}}
 
Zsigmondy:4,1,n {3, {5}, {7}, {17}, {341}, {13}, {5461}, {257}, {1387}, {41}}
 
Zsigmondy:5,1,n {4, {3}, {31}, {13}, {781}, {7}, {19531}, {313}, {15751}, {521}}
 
Zsigmondy:6,1,n {5, {7}, {43}, {37}, {311}, {31}, {55987}, {1297}, {46873}, {1111}}
 
Zsigmondy:7,1,n {6, {1}, {19}, {25}, {2801}, {43}, {137257}, {1201}, {39331}, {2101}}
 
Zsigmondy:3,2,n {1, {5}, {19}, {13}, {211}, {7}, {2059}, {97}, {1009}, {11}}
 
Zsigmondy:5,3,n {2, {1}, {49}, {17}, {1441}, {19}, {37969}, {353}, {19729}, {421}}
 
Zsigmondy:7,3,n {4, {5}, {79}, {29}, {4141}, {37}, {205339}, {1241}, {127639}, {341}}
 
Zsigmondy:7,5,n {2, {3}, {109}, {37}, {6841}, {13}, {372709}, {1513}, {176149}, {1661}}
</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}}==
{{trans|Raku}}
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use v5.36;
use experimental 'for_list';
use ntheory <gcd divisors vecall>;
 
sub Zsigmondy ($A, $B, $c) {
my @aexp = map { $A ** $_ } 0..$c;
my @bexp = map { $B ** $_ } 0..$c;
my @z;
for my $n (1..$c) {
for my $d (sort { $b <=> $a } divisors $aexp[$n] - $bexp[$n]) {
push @z, $d and last if vecall { gcd($aexp[$_] - $bexp[$_], $d) == 1 } 1..$n-1
}
return @z if 20 == @z
}
}
 
for my($name,$a,$b) (
'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,
) {
say "\n$name:\n" . join ' ', 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|Phix}}==
Line 325 ⟶ 1,002:
 
sub Zsigmondy ($a, $b) {
my @aexp = 1, $a, * × $a … *;
my @bexp = 1, $b, * × $b … *;
(1..∞).map: -> $n {
my @divisors = divisors(@aexp[$n] - @bexp[$n]).&divisors.sort(-*).first: -*;> $d {
@divisors.first: -> $d { all (1..^$n).map: -> $m { (@aexp[$m_] - @bexp[$m_]) gcd $d == 1 } }
}
}
}
 
for '064078', (2,1), '064079', (3,1), '064080', (4,1), '064081', (5,1), '064082', (6,1),
for 'A064078: Zsigmondy(n,2,1)', (2,1),
'064083', (7,1), '109325', (3,2), '109347', (5,3), '109348', (7,3), '109349', (7,5)
'A064079: Zsigmondy(n,3,1)', (3,1),
-> $oeis, $seq {
'A064080: Zsigmondy(n,4,1)', (4,1),
'A064081say "\nA$oeis: Zsigmondy(n,5$seq[0],$seq[1])',:\n" ~ Zsigmondy(5,1|$seq),[^20]
}</syntaxhighlight>
'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)
-> $name, $seq { say "\n$name:\n" ~ Zsigmondy(|$seq)[^20] }</syntaxhighlight>
{{out}}
<pre>A064078: Zsigmondy(n,2,1):
Line 374 ⟶ 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 379 ⟶ 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 431 ⟶ 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 441 ⟶ 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,032

edits

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