Fermat numbers: Difference between revisions
→{{header|langur}}
(→Wren-cli: Factorization routines are now built-in to BigInt.) |
Langurmonkey (talk | contribs) |
||
| (12 intermediate revisions by 6 users not shown) | |||
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 210 ⟶ 302:
=={{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"
Line 231 ⟶ 323:
(cdr acc))
(cons (list d 1) acc)))))))))
</syntaxhighlight>
{{out}}
Line 254 ⟶ 346:
=={{header|Crystal
{{trans|Ruby}}
This uses the `factor` function from the `coreutils` library
Line 260 ⟶ 352:
https://www.gnu.org/software/coreutils/
https://en.wikipedia.org/wiki/GNU_Core_Utilities
<
def factors(n)
Line 273 ⟶ 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 305 ⟶ 397:
=={{header|Factor}}==
<
math.primes.factors sequences ;
Line 319 ⟶ 411:
"Factors of F%c: %[%d, %]%s\n" printf 1 +
] each drop
] 2bi</
{{out}}
<pre>
Line 355 ⟶ 447:
The timings are for my Intel Core i7-8565U laptop using Go 1.14.1 on Ubuntu 18.04.
<
import (
Line 715 ⟶ 807:
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</
{{out}}
Line 747 ⟶ 839:
=={{header|Haskell}}==
<
import Data.Bool (bool)
Line 782 ⟶ 874:
showFactors x
| 1 < length x = show x
| otherwise = "(prime)"</
{{Out}}
<pre>First 10 Fermats:
Line 839 ⟶ 931:
=={{header|Java}}==
<
import java.math.BigInteger;
import java.util.ArrayList;
Line 969 ⟶ 1,061:
}
</syntaxhighlight>
Output includes composite numbers attempted to factor with Pollard rho.
{{out}}
Line 1,017 ⟶ 1,109:
'''Preliminaries'''
<
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
Line 1,048 ⟶ 1,140:
| until( (. * .) > $n or ($n % . == 0); . + 2)
| . * . > $n
end;</
'''Fermat Numbers'''
<
. as $n
| (2 | power( 2 | power($n))) + 1;
Line 1,086 ⟶ 1,178:
then "F\($i) : rho-prime", " ... => \(if is_prime then "prime" else "not" end)"
else "F\($i) => \($factors)"
end )</
{{out}}
<pre>
Line 1,118 ⟶ 1,210:
=={{header|Julia}}==
<
fermat(n) = BigInt(2)^(BigInt(2)^n) + 1
Line 1,138 ⟶ 1,230:
factorfermats(9, true)
factorfermats(10)
</
<pre>
Fermat number F(0) is 3.
Line 1,162 ⟶ 1,254:
=={{header|Kotlin}}==
{{trans|Java}}
<
import kotlin.math.pow
Line 1,283 ⟶ 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,316 ⟶ 1,407:
}
}
</syntaxhighlight>
{{out}}
<pre>first 10 Fermat numbers
F₀ = 3
Line 1,343 ⟶ 1,433:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Fermat[n_] := 2^(2^n) + 1
Fermat /@ Range[0, 9]
Scan[FactorInteger /* Print, %]</
{{out}}
<pre>{3,5,17,257,65537,4294967297,18446744073709551617,340282366920938463463374607431768211457,115792089237316195423570985008687907853269984665640564039457584007913129639937,13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097}
Line 1,363 ⟶ 1,453:
{{trans|Kotlin}}
{{libheader|bignum}}
<
import bignum
import strformat
Line 1,474 ⟶ 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,515 ⟶ 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,535 ⟶ 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,562 ⟶ 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,612 ⟶ 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,672 ⟶ 1,822:
=={{header|PicoLisp}}==
<
(de **Mod (X Y N)
(let M 1
Line 1,771 ⟶ 1,921:
N
':
(if (isprime N) 'PRIME (factors N)) ) ) )</
{{out}}
<pre>
Line 1,798 ⟶ 1,948:
=={{header|Python}}==
===Procedural===
<
factors = []
i = 2
Line 1,823 ⟶ 1,973:
print("F{} -> IS PRIME".format(chr(i + 0x2080)))
else:
print("F{} -> FACTORS: {}".format(chr(i + 0x2080), fac))</
{{out}}
<pre>
Line 1,853 ⟶ 2,003:
===Functional===
{{Works with|Python|3.7}}
<
from itertools import count, islice
Line 1,989 ⟶ 2,139:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>First ten Fermat numbers:
Line 2,014 ⟶ 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 2,029 ⟶ 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 2,057 ⟶ 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 2,089 ⟶ 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 2,127 ⟶ 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 2,162 ⟶ 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 2,188 ⟶ 2,338:
=={{header|Ring}}==
<
decimals(0)
load "stdlib.ring"
Line 2,210 ⟶ 2,360:
see "done..." + nl
</syntaxhighlight>
Output:
<pre>
Line 2,227 ⟶ 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 2,244 ⟶ 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 2,275 ⟶ 2,425:
=={{header|Rust}}==
<
curr: u64,
last: u64,
Line 2,331 ⟶ 2,481:
println!("{} is{}prime", f, not_or_not);
}
}</
{{out}}
<pre>
Line 2,348 ⟶ 2,498:
===Alternative using rug crate===
Based on the C++ code, which was based on the Java solution.
<
// rug = "1.9"
Line 2,425 ⟶ 2,575:
println!();
}
}</
{{out}}
Line 2,455 ⟶ 2,605:
=={{header|Scala}}==
{{trans|Kotlin}}
<
import scala.collection.mutable.ListBuffer
Line 2,560 ⟶ 2,710:
def pollardRhoG(x: BigInt, n: BigInt): BigInt = ((x * x) + 1) % n
}</
{{out}}
<pre>First 10 Fermat numbers:
Line 2,602 ⟶ 2,752:
=={{header|Sidef}}==
<
2**(2**n) + 1
}
Line 2,620 ⟶ 2,770:
say ("F_#{n} = ", join(' * ', f.shift,
f.map { <C P>[.is_prime] + .len }...))
}</
{{out}}
<pre>
Line 2,651 ⟶ 2,801:
=={{header|Tcl}}==
<
package require math::numtheory 1.1.1; # Buggy before tcllib-1.20
Line 2,673 ⟶ 2,823:
puts "factors: $factors"
}
}</
{{out}}
Line 2,700 ⟶ 2,850:
{{libheader|Wren-big}}
The first seven Fermat numbers are factorized in about 0.75 seconds but as it would take 'hours' to get any further I've stopped there.
<
var fermat = Fn.new { |n| BigInt.two.pow(2.pow(n)) + 1 }
Line 2,723 ⟶ 2,873:
System.print()
}
}</
{{out}}
Line 2,755 ⟶ 2,905:
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.
<
import "./gmp" for Mpz
Line 2,784 ⟶ 2,934:
}
System.print("\nThe first factor of F₉ is %(Mpz.pollardRho(fns[9])).")</
{{out}}
Line 2,808 ⟶ 2,958:
F₅ = [641, 6700417]
F₆ = [274177, 67280421310721]
F₇ = [59649589127497217, 5704689200685129054721]
F₈ = [1238926361552897, 93461639715357977769163558199606896584051237541638188580280321]
Line 2,816 ⟶ 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,833 ⟶ 2,984:
F9: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
</pre>
<
acc:=fcn(n,k,acc,maxD){ // k is primes
if(n==1 or k>maxD) acc.close();
Line 2,845 ⟶ 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>
| |||