Fermat numbers: Difference between revisions
→{{header|Wren}}: Added an embedded version which uses the new Wren-ecm module.
(→{{header|Wren}}: Added an embedded version which uses the new Wren-ecm module.) |
|||
Line 2,697:
=={{header|Wren}}==
===Wren-cli===
{{libheader|Wren-big}}
The first seven Fermat numbers are factorized in about 0.75 seconds by Pollard's Rho but as it would take 'hours' to get any further I've stopped there.
Line 2,777 ⟶ 2,778:
F₅ = [641, 6700417]
F₆ = [274177, 67280421310721]
</pre>
===Embedded===
{{libheader|Wren-gmp}}
{{libheader|Wren-ecm}}
This uses Lenstra's elliptical curve method (ECM) to find F₇ and Pollard's Rho to find the rest, including the first factor of F₉.
The overall time for this particular run was about 86 seconds with F₇ being found in only a couple of them. However, being non-deterministic, ECM is quite erratic time-wise and could take up to 3 minutes longer.
<lang ecmascript>/* fermat_numbers_gmp.wren */
import "./gmp" for Mpz
import "./ecm" for Ecm
import "random" for Random
var fermat = Fn.new { |n| Mpz.two.pow(2.pow(n)) + 1 }
var fns = List.filled(10, null)
System.print("The first 10 Fermat numbers are:")
for (i in 0..9) {
fns[i] = fermat.call(i)
System.print("F%(String.fromCodePoint(0x2080+i)) = %(fns[i])")
}
System.print("\nFactors of the first 8 Fermat numbers:")
for (i in 0..8) {
if (i == 7) continue
System.write("F%(String.fromCodePoint(0x2080+i)) = ")
var factors = (i != 7) ? Mpz.primeFactors(fns[i]) : Ecm.primeFactors(fns[i])
System.write("%(factors)")
if (factors.count == 1) {
System.print(" (prime)")
} else if (!factors[1].probPrime(15)) {
System.print(" (second factor is composite)")
} else {
System.print()
}
}
System.print("\nThe first factor of F₉ is %(Mpz.pollardRho(fns[9])).")</lang>
{{out}}
<pre>
The first 10 Fermat numbers are:
F₀ = 3
F₁ = 5
F₂ = 17
F₃ = 257
F₄ = 65537
F₅ = 4294967297
F₆ = 18446744073709551617
F₇ = 340282366920938463463374607431768211457
F₈ = 115792089237316195423570985008687907853269984665640564039457584007913129639937
F₉ = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
Factors of the first 8 Fermat numbers:
F₀ = [3] (prime)
F₁ = [5] (prime)
F₂ = [17] (prime)
F₃ = [257] (prime)
F₄ = [65537] (prime)
F₅ = [641, 6700417]
F₆ = [274177, 67280421310721]
F₈ = [1238926361552897, 93461639715357977769163558199606896584051237541638188580280321]
The first factor of F₉ is 2424833.
</pre>
| |||