Zsigmondy numbers: Difference between revisions
→{{header|jq}}
Thundergnat (talk | contribs) m (→{{header|Raku}}: minor simplification) |
|||
Line 188:
=={{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 234 ⟶ 338:
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}}==
| |||