Euclid-Mullin sequence: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added mpz_set_v()) |
(→{{header|Wren}}: Added an embedded version using Wren-gmp.) |
||
| Line 180: | Line 180: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
===Wren-cli=== |
|||
This uses the [https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm Pollard Rho algorithm] to try and speed up the factorization of the 15th element but overall time still slow at around 32 seconds. |
This uses the [https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm Pollard Rho algorithm] to try and speed up the factorization of the 15th element but overall time still slow at around 32 seconds. |
||
<lang ecmascript>import "./big" for BigInt |
<lang ecmascript>import "./big" for BigInt |
||
| Line 280: | Line 281: | ||
52662739 |
52662739 |
||
23003 |
23003 |
||
</pre> |
|||
<br> |
|||
===Embedded=== |
|||
{{libheader|Wren-gmp}} |
|||
This finds the first 16 in 0.11 seconds and the next 3 in around 39 seconds. I gave up after that as it would take too long for the Pollard's Rho algorithm to find any more. |
|||
<lang ecmascript>/* euclid_mullin_gmp.wren */ |
|||
import "./gmp" for Mpz |
|||
var max = Mpz.from(100000) |
|||
var smallestPrimeFactorWheel = Fn.new { |n| |
|||
if (n.probPrime(15) > 0) return n |
|||
if (n.isEven) return Mpz.two |
|||
if (n.isDivisibleUi(3)) return Mpz.three |
|||
if (n.isDivisibleUi(5)) return Mpz.five |
|||
var k = Mpz.from(7) |
|||
var i = 0 |
|||
var inc = [4, 2, 4, 2, 4, 6, 2, 6] |
|||
while (k * k <= n) { |
|||
if (n.isDivisible(k)) return k |
|||
k.add(inc[i]) |
|||
if (k > max) return null |
|||
i = (i + 1) % 8 |
|||
} |
|||
} |
|||
var smallestPrimeFactor = Fn.new { |n| |
|||
var s = smallestPrimeFactorWheel.call(n) |
|||
if (s) return s |
|||
var c = Mpz.one |
|||
s = n.copy() |
|||
while (n > max) { |
|||
var d = Mpz.pollardRho(n, 2, c) |
|||
if (d.isZero) { |
|||
if (c == 100) Fiber.abort("Pollard Rho doesn't appear to be working.") |
|||
c.inc |
|||
} else { |
|||
// can't be sure PR will find the smallest prime factor first |
|||
s.min(d) |
|||
n.div(d) |
|||
if (n.probPrime(5) > 0) return Mpz.min(s, n) |
|||
} |
|||
} |
|||
return s |
|||
} |
|||
var k = 19 |
|||
System.print("First %(k) terms of the Euclid–Mullin sequence:") |
|||
System.print(2) |
|||
var prod = Mpz.two |
|||
var count = 1 |
|||
while (count < k) { |
|||
var t = smallestPrimeFactor.call(prod + Mpz.one) |
|||
System.print(t) |
|||
prod.mul(t) |
|||
count = count + 1 |
|||
}</lang> |
|||
{{out}} |
|||
As Wren-cli plus three more: |
|||
<pre> |
|||
30693651606209 |
|||
37 |
|||
1741 |
|||
</pre> |
</pre> |
||