Zsigmondy numbers: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: More specific.) |
(→{{header|Wren}}: Added a BigInt version.) |
||
Line 270: | Line 270: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
===Normal arithmetic=== |
|||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Line 329: | Line 330: | ||
Zsigmony(n, 7, 5) - first 18 terms: |
Zsigmony(n, 7, 5) - first 18 terms: |
||
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 |
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 |
||
</pre> |
|||
===BigInt=== |
|||
{{libheader|Wren-big}} |
|||
{{libheader|Wren-seq}} |
|||
However, we can deal with integers of any size by switching to BigInt. |
|||
<syntaxhighlight lang="ecmascript"> |
|||
import "./big" for BigInt |
|||
import "./seq" for Lst |
|||
import "./fmt" for Fmt |
|||
var divisors = Fn.new { |n| |
|||
var factors = BigInt.primeFactors(n) |
|||
var divs = [BigInt.one] |
|||
for (p in factors) { |
|||
for (i in 0...divs.count) divs.add(divs[i]*p) |
|||
} |
|||
return Lst.prune(divs.sort { |i, j| i >= j }) |
|||
} |
|||
var zs = Fn.new { |n, a, b| |
|||
a = BigInt.new(a) |
|||
b = BigInt.new(b) |
|||
var dn = a.pow(n) - b.pow(n) |
|||
if (dn.isPrime) return dn |
|||
var divs = divisors.call(dn) |
|||
var dms = (1...n).map { |m| a.pow(m) - b.pow(m) }.toList |
|||
for (div in divs) { |
|||
if (dms.all { |dm| BigInt.gcd(dm, div) == 1 }) return div |
|||
} |
|||
return BigInt.one |
|||
} |
|||
var abs = [ [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [3, 2], [5, 3], [7, 3], [7, 5] ] |
|||
var lim = 20 |
|||
for (ab in abs) { |
|||
var a = ab[0] |
|||
var b = ab[1] |
|||
System.print("Zsigmony(n, %(a), %(b)) - first %(lim) terms:") |
|||
Fmt.print("$i", (1..lim).map { |n| zs.call(n, a, b) }.toList) |
|||
System.print() |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Zsigmony(n, 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(n, 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(n, 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(n, 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(n, 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(n, 7, 1) - first 20 terms: |
|||
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307 1899815864228857 1129901 |
|||
Zsigmony(n, 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(n, 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(n, 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(n, 7, 5) - first 20 terms: |
|||
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201 |
|||
</pre> |
</pre> |