Fermat numbers: Difference between revisions
→{{header|langur}}
m (→{{header|Phix}}: added syntax colouring the hard way) |
Langurmonkey (talk | contribs) |
||
| (20 intermediate revisions by 11 users not shown) | |||
Line 1:
{{task|Prime Numbers}}
In mathematics, a Fermat number, ''named after Pierre de Fermat who first studied them,'' is a positive integer of the form <big>'''F<sub>n</sub> = 2<sup>''2''<sup>''n''</sup></sup> + 1'''</big> where '''n''' is a non-negative integer.
Line 24:
<br>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.
{{libheader|ALGOL 68-primes}}
The source of primes.incl.a68 is on another page on Rosetta Code, see the above link.
<syntaxhighlight lang="algol68">
BEGIN # find and factorise some Fermat numbers: F(n) = 2^(2^n) + 1 #
PR read "primes.incl.a68" PR # include prime utilities #
PR precision 256 PR # set the precision of LONG LONG INT #
PROC gcd = ( LONG LONG INT x, y )LONG LONG INT: # iterative gcd #
BEGIN
LONG LONG INT a := x, b := y;
WHILE b /= 0 DO
LONG LONG INT next a = b;
b := a MOD b;
a := next a
OD;
ABS a
END # gcd # ;
# returns a prime factor (if possible) of n, if n is prime, n is returned #
PROC pollard rho = ( LONG LONG INT n )LONG LONG INT:
IF is probably prime( n )
THEN n
ELIF LONG LONG INT x := 2, y := 2, d := 1;
PROC g = ( LONG LONG INT x )LONG LONG INT: ( ( x * x ) + 1 ) MOD n;
WHILE d = 1 DO
x := g( x );
y := g( g( y ) );
d := gcd( ABS( x - y ), n )
OD;
d = n
THEN print( ( "pollard rho found non probably prime n for: ", n, newline ) );
n
ELIF LONG LONG INT other d = n OVER d;
d > other d
THEN other d
ELSE d
FI # pollard rho # ;
# returns the lowest prime factor of n, or n if n is prime #
PROC prime factor = ( LONG LONG INT n )LONG LONG INT:
IF LONG LONG INT d := pollard rho( n );
d = n
THEN d
ELSE # check for a lower factor #
LONG LONG INT other d := n OVER d;
LONG LONG INT d1 := pollard rho( other d );
WHILE d1 < d DO
d := d1;
other d := other d OVER d;
d1 := pollard rho( other d )
OD;
IF d1 < d THEN d1 ELSE d FI
FI # prime factor # ;
# task #
INT p2 := 1;
FOR i FROM 0 TO 9 DO
LONG LONG INT fn = 1 + ( LONG LONG 2 )^p2;
print( ( "F(", whole( i, 0 ), "): ", whole( fn, 0 ) ) );
IF i < 7 THEN
print( ( ", " ) );
LONG LONG INT pf = prime factor( fn );
IF pf = fn THEN
print( ( "prime" ) )
ELSE
print( ( whole( pf, 0 ), " x ", whole( fn OVER pf, 0 ) ) )
FI
FI;
print( ( newline ) );
p2 *:= 2
OD
END
</syntaxhighlight>
{{out}}
<pre>
F(0): 3, prime
F(1): 5, prime
F(2): 17, prime
F(3): 257, prime
F(4): 65537, prime
F(5): 4294967297, 641 x 6700417
F(6): 18446744073709551617, 274177 x 67280421310721
F(7): 340282366920938463463374607431768211457
F(8): 115792089237316195423570985008687907853269984665640564039457584007913129639937
F(9): 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
</pre>
=={{header|Arturo}}==
<
fermatSet: map 0..9 'x -> 1 + 2 ^ nPowers\[x]
Line 35 ⟶ 127:
loop 0..9 'i ->
print ["Prime factors of F(" i ") =" factors.prime fermatSet\[i]]</
=={{header|C}}==
Compile with : <pre>gcc -o fermat fermat.c -lgmp</pre>
<
#include <stdio.h>
#include <gmp.h>
Line 79 ⟶ 171:
return 0;
}</
<pre>
F(0) = 3 -> PRIME
Line 98 ⟶ 190:
Built and tested on macOS 10.15, CPU: 3.2 GHz Intel Core i5.
Execution time is about 12 minutes.
<
#include <vector>
#include <boost/integer/common_factor.hpp>
Line 180 ⟶ 272:
}
return 0;
}</
{{out}}
Line 208 ⟶ 300:
</pre>
=={{header|Common Lisp}}==
{{trans|Lisp}}
This uses the 'factor' function defined in the page Prime Decomposition
http://rosettacode.org/wiki/Prime_decomposition#Common_Lisp
<syntaxhighlight lang="lisp">
(defun fermat-number (n)
"Return the n-th Fermat number"
(1+ (expt 2 (expt 2 n))) )
(defun factor (n &optional (acc '()))
"Return the list of factors of n"
(when (> n 1) (loop with max-d = (isqrt n)
for d = 2 then (if (evenp d) (1+ d) (+ d 2)) do
(cond ((> d max-d) (return (cons (list n 1) acc)))
((zerop (rem n d))
(return (factor (truncate n d) (if (eq d (caar acc))
(cons
(list (caar acc) (1+ (cadar acc)))
(cdr acc))
(cons (list d 1) acc)))))))))
</syntaxhighlight>
{{out}}
<pre>
(dotimes (i 8) (format t "~d: ~d = ~d~%" i (fermat-number i) (factors (fermat-number i))))
0: 3 = (3)
1: 5 = (5)
2: 17 = (17)
3: 257 = (257)
4: 65537 = (65537)
5: 4294967297 = (641 6700417)
6: 18446744073709551617 = (274177 (67280421310721))
7: 340282366920938463463374607431768211457 = ((340282366920938463463374607431768211457))
8: 115792089237316195423570985008687907853269984665640564039457584007913129639937 = ((115792089237316195423570985008687907853269984665640564039457584007913129639937))
9: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 = ((13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097))
10: 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217 = ((179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217))
11: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230657 = (319489
(101152171346465785365739905563790778275446424351747584524444802254614885454171789617787158279386499891040749324458425859713854183244152133860909616251101863039512713637405344446131784663602352840930541077733717180487566766438342966931062084574042206368862921265008513729385286790910065162204496552694867070609361616173540692858549041708993328392702647150062512506151403207406283761595736673720405375033810606080158013948717662760215065784116654734290374983906448207065425365852408720566771005345821995341556493590254118091846659097349200248570452085641250044738949182704974520704370036542579394575574913724915713))
12: 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190337 = (114689
(9106268965752186405773463110818163752233991481723476361152625650968740750826648212547208641935996986118024454955917854702609434541985662158212523327009262247869952450049350838706079834460006786304075107567909269645531121898331250125751682239313156601738683820643686003638396435055834553570682260579462973839574318172464558815116581626749391315641251152532705571615644886981829338611134458123396450764186936496833100701185274214915961723337127995182593580031119299575446791424418154036863609858251201843852076223383379133238000289598800458955855329052103961332983048473420515918928565951506637819342706575976725030506905683310915700945442329953941604008255667676914945655757474715779252371155778495946746587469464160684843488975918662295274965457887082037460184558511575570318625886351712499453155527762335682281851520733417380809781252979478377941937578568481859702438295520231435016188495646093490407803983345420364088331996467459309353537828143080691834120737157445502646809195267166779721413577366833939771467773331873590129210913628329073978766992198221682739812652450408607796042492802295258713711959073218748776359806123717024800451461326745599716651128725627280643537507664130920416107218492950792456907321580171946770433))</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
This uses the `factor` function from the `coreutils` library
Line 214 ⟶ 352:
https://www.gnu.org/software/coreutils/
https://en.wikipedia.org/wiki/GNU_Core_Utilities
<
def factors(n)
Line 227 ⟶ 365:
puts
puts "Factors for each Fermat Number F0 .. F8."
(0..8).each { |n| puts "F#{n} = #{factors fermat(n)}" }</
System: Lenovo V570 (2011), I5-2410M, 2.9 GHz, Crystal 0.34
Line 259 ⟶ 397:
=={{header|Factor}}==
<
math.primes.factors sequences ;
Line 273 ⟶ 411:
"Factors of F%c: %[%d, %]%s\n" printf 1 +
] each drop
] 2bi</
{{out}}
<pre>
Line 309 ⟶ 447:
The timings are for my Intel Core i7-8565U laptop using Go 1.14.1 on Ubuntu 18.04.
<
import (
Line 669 ⟶ 807:
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</
{{out}}
Line 701 ⟶ 839:
=={{header|Haskell}}==
<
import Data.Bool (bool)
Line 736 ⟶ 874:
showFactors x
| 1 < length x = show x
| otherwise = "(prime)"</
{{Out}}
<pre>First 10 Fermats:
Line 793 ⟶ 931:
=={{header|Java}}==
<
import java.math.BigInteger;
import java.util.ArrayList;
Line 923 ⟶ 1,061:
}
</syntaxhighlight>
Output includes composite numbers attempted to factor with Pollard rho.
{{out}}
Line 966 ⟶ 1,104:
F[12] = 114689 * 26017793 * 63766529 * (C1213)
</pre>
=={{header|jq}}==
'''Works with gojq, the Go implementation of jq'''
'''Preliminaries'''
<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
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;
# This is fast because the state of `until` is just a number
def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
elif ($n % 23 == 0) then $n == 23
elif ($n % 29 == 0) then $n == 29
elif ($n % 31 == 0) then $n == 31
elif ($n % 37 == 0) then $n == 37
elif ($n % 41 == 0) then $n == 41
else 43
| until( (. * .) > $n or ($n % . == 0); . + 2)
| . * . > $n
end;</syntaxhighlight>
'''Fermat Numbers'''
<syntaxhighlight lang="jq">def fermat:
. as $n
| (2 | power( 2 | power($n))) + 1;
# https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
def pollardRho($x):
. as $n
| def g: (.*. + 1) % $n ;
{x:$x, y:$x, d:1}
| until(.d != 1;
.x |= g
| .y |= (g|g)
| .d = gcd((.x - .y)|length; $n) )
| if .d == $n then 0
else .d
end ;
def rhoPrimeFactors:
. as $n
| pollardRho(2)
| if . == 0
then [$n, 1]
else [., ($n / .)]
end ;
"The first 10 Fermat numbers are:",
[ range(0;10) | fermat ] as $fns
| (range(0;10) | "F\(.) is \($fns[.])"),
("\nFactors of the first 7 Fermat numbers:",
range(0;7) as $i
| $fns[$i]
| rhoPrimeFactors as $factors
| if $factors[1] == 1
then "F\($i) : rho-prime", " ... => \(if is_prime then "prime" else "not" end)"
else "F\($i) => \($factors)"
end )</syntaxhighlight>
{{out}}
<pre>
The first 10 Fermat numbers are:
F0 is 3
F1 is 5
F2 is 17
F3 is 257
F4 is 65537
F5 is 4294967297
F6 is 18446744073709551617
F7 is 340282366920938463463374607431768211457
F8 is 115792089237316195423570985008687907853269984665640564039457584007913129639937
F9 is 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
Factors of the first 7 Fermat numbers:
F0 : rho-prime
... => prime
F1 : rho-prime
... => prime
F2 : rho-prime
... => prime
F3 : rho-prime
... => prime
F4 : rho-prime
... => prime
F5 => [641,6700417]
F6 => [274177,67280421310721]
</pre>
=={{header|Julia}}==
<
fermat(n) = BigInt(2)^(BigInt(2)^n) + 1
Line 988 ⟶ 1,230:
factorfermats(9, true)
factorfermats(10)
</
<pre>
Fermat number F(0) is 3.
Line 1,012 ⟶ 1,254:
=={{header|Kotlin}}==
{{trans|Java}}
<
import kotlin.math.pow
Line 1,133 ⟶ 1,375:
private fun pollardRhoG(x: BigInteger, n: BigInteger): BigInteger {
return (x * x + BigInteger.ONE).mod(n)
}</
=={{header|langur}}==
{{trans|Python}}
<syntaxhighlight lang="langur">val .fermat = fn(.i) { 2 ^ 2 ^ .i + 1 }
val .factors =
for[.f=[]] .i, .s = 2,
if .x div .i {
.f ~= [.i]
.x \= .i
.s =
}
} ~ [.x]
Line 1,166 ⟶ 1,407:
}
}
</syntaxhighlight>
{{out}}
<pre>first 10 Fermat numbers
F₀ = 3
Line 1,191 ⟶ 1,431:
F₆ factors: [274177, 67280421310721]
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[Fermat]
Fermat[n_] := 2^(2^n) + 1
Fermat /@ Range[0, 9]
Scan[FactorInteger /* Print, %]</syntaxhighlight>
{{out}}
<pre>{3,5,17,257,65537,4294967297,18446744073709551617,340282366920938463463374607431768211457,115792089237316195423570985008687907853269984665640564039457584007913129639937,13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097}
{{3,1}}
{{5,1}}
{{17,1}}
{{257,1}}
{{65537,1}}
{{641,1},{6700417,1}}
{{274177,1},{67280421310721,1}}
{{59649589127497217,1},{5704689200685129054721,1}}
{{1238926361552897,1},{93461639715357977769163558199606896584051237541638188580280321,1}}
$Aborted</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
<
import bignum
import strformat
Line 1,306 ⟶ 1,564:
echo "First 12 Fermat numbers factored:"
for i in 0..12:
echo fmt"F{subscript(i)} = {factors(i, fermat(i))}"</
{{out}}
Line 1,347 ⟶ 1,605:
Pollard rho try factor 350001591824186871106763863899530746217943677302816436473017740242946077356624684213115564488348300185108877411543625345263121839042445381828217455916005721464151569276047005167043946981206545317048033534893189043572263100806868980998952610596646556521480658280419327021257968923645235918768446677220584153297488306270426504473941414890547838382804073832577020334339845312084285496895699728389585187497914849919557000902623608963141559444997044721763816786117073787751589515083702681348245404913906488680729999788351730419178916889637812821243344085799435845038164784900107242721493170135785069061880328434342030106354742821995535937481028077744396075726164309052460585559946407282864168038994640934638329525854255227752926198464207255983432778402344965903148839661825873175277621985527846249416909718758069997783882773355041329208102046913755441975327368023946523920699020098723785533557579080342841062805878477869513695185309048285123705067072486920463781103076554014502567884803571416673251784936825115787932810954867447447568320403976197134736485611912650805539603318790667901618038578533362100071745480995207732506742832634459994375828162163700807237997808869771569154136465922798310222055287047244647419069003284481 elapsed time = 114 ms (factor = 63766529).
F₁₂ = 114689 * 26017793 * 63766529 * (C1213)</pre>
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
\\ Define a function to calculate Fermat numbers
fermat(n) = 2^(2^n) + 1;
\\ Define a function to factor Fermat numbers up to a given maximum
\\ and optionally just print them without factoring
factorfermats(mymax, nofactor=0) =
{
local(fm, factors, n);
for (n = 0, mymax,
fm = fermat(n);
if (nofactor,
print("Fermat number F(", n, ") is ", fm, ".");
next;
);
factors = factorint(fm);
if (matsize(factors)[1] == 1 && factors[1,2] == 1, \\ Check if it has only one factor with exponent 1 (i.e., prime)
print("Fermat number F(", n, "), ", fm, ", is prime.");
,
print("Fermat number F(", n, "), ", fm, ", factors to ", (factors), ".");
);
);
}
{
\\ Example usage
factorfermats(9, 1); \\ Print Fermat numbers without factoring
print(""); \\ Just to add a visual separator in the output
factorfermats(10); \\ Factor Fermat numbers
}
</syntaxhighlight>
{{out}}
<pre>
Fermat number F(0) is 3.
Fermat number F(1) is 5.
Fermat number F(2) is 17.
Fermat number F(3) is 257.
Fermat number F(4) is 65537.
Fermat number F(5) is 4294967297.
Fermat number F(6) is 18446744073709551617.
Fermat number F(7) is 340282366920938463463374607431768211457.
Fermat number F(8) is 115792089237316195423570985008687907853269984665640564039457584007913129639937.
Fermat number F(9) is 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097.
Fermat number F(0), 3, is prime.
Fermat number F(1), 5, is prime.
Fermat number F(2), 17, is prime.
Fermat number F(3), 257, is prime.
Fermat number F(4), 65537, is prime.
Fermat number F(5), 4294967297, factors to [641, 1; 6700417, 1].
Fermat number F(6), 18446744073709551617, factors to [274177, 1; 67280421310721, 1].
Fermat number F(7), 340282366920938463463374607431768211457, factors to [59649589127497217, 1; 5704689200685129054721, 1].
Fermat number F(8), 115792089237316195423570985008687907853269984665640564039457584007913129639937, factors to [1238926361552897, 1; 93461639715357977769163558199606896584051237541638188580280321, 1].
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 1,367 ⟶ 1,685:
for my $f (map { [factor($_)] } @Fermats[0..8]) {
printf "Factors of F%s: %s\n", $sub++, @$f == 1 ? 'prime' : join ' ', @$f
}</
{{out}}
<pre>First 10 Fermat numbers:
Line 1,394 ⟶ 1,712:
=={{header|Phix}}==
{{libheader|Phix/mpfr}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Fermat.exw</span>
Line 1,444 ⟶ 1,762:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Factors of F%d: %s [%s]\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ts</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
Note that mpz_prime_factors(), a phix-specific extension to gmp, is designed to find small factors quickly and
Line 1,501 ⟶ 1,819:
Factors of F12: 114689*910626896...<1,228 digits>...946770433 (last factor is not prime) [0.6s]
Factors of F13: 109074813...<2,467 digits>...715792897 (not prime) [1.3s]
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(seed (in "/dev/urandom" (rd 8)))
(de **Mod (X Y N)
(let M 1
(loop
(when (bit? 1 Y)
(setq M (% (* M X) N)) )
(T (=0 (setq Y (>> 1 Y)))
M )
(setq X (% (* X X) N)) ) ) )
(de isprime (N)
(cache '(NIL) N
(if (== N 2)
T
(and
(> N 1)
(bit? 1 N)
(let (Q (dec N) N1 (dec N) K 0 X)
(until (bit? 1 Q)
(setq
Q (>> 1 Q)
K (inc K) ) )
(catch 'composite
(do 16
(loop
(setq X
(**Mod
(rand 2 (min (dec N) 1000000000000))
Q
N ) )
(T (or (=1 X) (= X N1)))
(T
(do K
(setq X (**Mod X 2 N))
(when (=1 X) (throw 'composite))
(T (= X N1) T) ) )
(throw 'composite) ) )
(throw 'composite T) ) ) ) ) ) )
(de gcd (A B)
(until (=0 B)
(let M (% A B)
(setq A B B M) ) )
(abs A) )
(de g (A)
(% (+ (% (* A A) N) C) N) )
(de pollard-brent (N)
(let
(A (dec N)
Y (rand 1 (min A 1000000000000000000))
C (rand 1 (min A 1000000000000000000))
M (rand 1 (min A 1000000000000000000))
G 1
R 1
Q 1 )
(ifn (bit? 1 N)
2
(loop
(NIL (=1 G))
(setq X Y)
(do R
(setq Y (g Y)) )
(zero K)
(loop
(NIL (and (> R K) (=1 G)))
(setq YS Y)
(do (min M (- R K))
(setq
Y (g Y)
Q (% (* Q (abs (- X Y))) N) ) )
(setq
G (gcd Q N)
K (+ K M) )
)
(setq R (* R 2)) )
(when (== G N)
(loop
(NIL (> G 1))
(setq
YS (g YS)
G (gcd (abs (- X YS)) N) ) ) )
(if (== G N)
NIL
G ) ) ) )
(de factors (N)
(sort
(make
(loop
(setq N (/ N (link (pollard-brent N))))
(T (isprime N)) )
(link N) ) ) )
(de fermat (N)
(inc (** 2 (** 2 N))) )
(for (N 0 (>= 8 N) (inc N))
(println N ': (fermat N)) )
(prinl)
(for (N 0 (>= 8 N) (inc N))
(let N (fermat N)
(println
N
':
(if (isprime N) 'PRIME (factors N)) ) ) )</syntaxhighlight>
{{out}}
<pre>
$ pil VU.l
0 : 3
1 : 5
2 : 17
3 : 257
4 : 65537
5 : 4294967297
6 : 18446744073709551617
7 : 340282366920938463463374607431768211457
8 : 115792089237316195423570985008687907853269984665640564039457584007913129639937
3 : PRIME
5 : PRIME
17 : PRIME
257 : PRIME
65537 : PRIME
4294967297 : (641 6700417)
18446744073709551617 : (274177 67280421310721)
340282366920938463463374607431768211457 : (59649589127497217 5704689200685129054721)
115792089237316195423570985008687907853269984665640564039457584007913129639937 : (1238926361552897 93461639715357977769163558199606896584051237541638188580280321)
</pre>
=={{header|Python}}==
===Procedural===
<
factors = []
i = 2
Line 1,530 ⟶ 1,973:
print("F{} -> IS PRIME".format(chr(i + 0x2080)))
else:
print("F{} -> FACTORS: {}".format(chr(i + 0x2080), fac))</
{{out}}
<pre>
Line 1,560 ⟶ 2,003:
===Functional===
{{Works with|Python|3.7}}
<
from itertools import count, islice
Line 1,696 ⟶ 2,139:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>First ten Fermat numbers:
Line 1,721 ⟶ 2,164:
=={{header|Raku}}==
(formerly Perl 6)
I gave up on factoring F₉ after about 20 minutes.
{{libheader|ntheory}}
<syntaxhighlight lang="raku" line>use ntheory:from<Perl5> <factor>;
my @Fermats = (^Inf).map: 2 ** 2 ** * + 1;
Line 1,736 ⟶ 2,179:
for @Fermats[^9].map( {"$_".&factor} ) -> $f {
printf "Factors of F%s: %s %s\n", $sub++, $f.join(' '), $f.elems == 1 ?? '- prime' !! ''
}</
{{out}}
<pre>First 10 Fermat numbers:
Line 1,764 ⟶ 2,207:
=={{header|REXX}}==
=== factoring by trial division ===
<
parse arg n . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 9 /*Not specified? Then use the default.*/
Line 1,796 ⟶ 2,239:
return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
build: do while z//j==0; z= z % j; ?= ? j; end; return strip(?)</
{{out|output|text= when using the default input:}}
<pre>
Line 1,834 ⟶ 2,277:
=== factoring via Pollard's rho algorithm ===
<
parse arg n . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 9 /*Not specified? Then use the default.*/
Line 1,869 ⟶ 2,312:
end /*while*/
end /*x*/
return d /*found a factor of N. Return it.*/</
{{out|output|text= when using the default input:}}
<pre>
Line 1,895 ⟶ 2,338:
=={{header|Ring}}==
<
decimals(0)
load "stdlib.ring"
Line 1,917 ⟶ 2,360:
see "done..." + nl
</syntaxhighlight>
Output:
<pre>
Line 1,934 ⟶ 2,377:
</pre>
=={{header|Ruby
This uses the `factor` function from the `coreutils` library
that comes standard with most GNU/Linux, BSD, and Unix systems.
https://www.gnu.org/software/coreutils/
https://en.wikipedia.org/wiki/GNU_Core_Utilities
<
factors = `factor #{n}`.split(' ')[1..-1].map(&:to_i)
factors.group_by { _1 }.map { |prime, exp| [prime, exp.size] } # Ruby 2.7 or later
Line 1,951 ⟶ 2,394:
puts
puts "Factors for each Fermat Number F0 .. F8."
(0..8).each { |n| puts "F#{n} = #{factors fermat(n)}" }</
System: Lenovo V570 (2011), I5-2410M, 2.9 GHz, Ruby 2.7.1
Line 1,982 ⟶ 2,425:
=={{header|Rust}}==
<
curr: u64,
last: u64,
Line 2,038 ⟶ 2,481:
println!("{} is{}prime", f, not_or_not);
}
}</
{{out}}
<pre>
Line 2,055 ⟶ 2,498:
===Alternative using rug crate===
Based on the C++ code, which was based on the Java solution.
<
// rug = "1.9"
Line 2,132 ⟶ 2,575:
println!();
}
}</
{{out}}
Line 2,162 ⟶ 2,605:
=={{header|Scala}}==
{{trans|Kotlin}}
<
import scala.collection.mutable.ListBuffer
Line 2,267 ⟶ 2,710:
def pollardRhoG(x: BigInt, n: BigInt): BigInt = ((x * x) + 1) % n
}</
{{out}}
<pre>First 10 Fermat numbers:
Line 2,309 ⟶ 2,752:
=={{header|Sidef}}==
<
2**(2**n) + 1
}
Line 2,327 ⟶ 2,770:
say ("F_#{n} = ", join(' * ', f.shift,
f.map { <C P>[.is_prime] + .len }...))
}</
{{out}}
<pre>
Line 2,358 ⟶ 2,801:
=={{header|Tcl}}==
<
package require math::numtheory 1.1.1; # Buggy before tcllib-1.20
Line 2,380 ⟶ 2,823:
puts "factors: $factors"
}
}</
{{out}}
Line 2,404 ⟶ 2,847:
=={{header|Wren}}==
===Wren-cli===
{{libheader|Wren-big}}
The first seven Fermat numbers are factorized in about 0.75 seconds
<
var fermat = Fn.new { |n| BigInt.two.pow(2.pow(n)) + 1 }
var fns = List.filled(10, null)
Line 2,451 ⟶ 2,864:
for (i in 0..6) {
System.write("F%(String.fromCodePoint(0x2080+i)) = ")
var factors =
System.write("%(factors)")
if (factors
System.print(" (prime)")
} else if (!factors[1].isProbablePrime(5)) {
Line 2,460 ⟶ 2,873:
System.print()
}
}</
{{out}}
Line 2,477 ⟶ 2,890:
Factors of the first 7 Fermat numbers:
F₀ = [3
F₁ = [5
F₂ = [17
F₃ = [257
F₄ = [65537
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.
<syntaxhighlight lang="wren">/* fermat_numbers_2.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) {
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])).")</syntaxhighlight>
{{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₇ = [59649589127497217, 5704689200685129054721]
F₈ = [1238926361552897, 93461639715357977769163558199606896584051237541638188580280321]
The first factor of F₉ is 2424833.
</pre>
Line 2,489 ⟶ 2,967:
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
for big ints and primes
<
println("First 10 Fermat numbers:");
foreach n in (10){ println("F",n,": ",fermatsW.next()) }</
{{out}}
<pre style="font-size:83%">
Line 2,506 ⟶ 2,984:
F9: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
</pre>
<
acc:=fcn(n,k,acc,maxD){ // k is primes
if(n==1 or k>maxD) acc.close();
Line 2,518 ⟶ 2,996:
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}</
<
println("Factors of first few Fermat numbers:");
foreach n in (7){
println("Factors of F",n,": ",factorsBI(fermatsW.next()).concat(" "));
}</
{{out}}
<pre>
| |||