Jump to content

Fermat numbers: Difference between revisions

Fermat numbers (view source)

Revision as of 11:26, 27 August 2022

1,048 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (→‎{{header|Raku}}: note use of 'ntheory' module)
m (syntax highlighting fixup automation)
Line 26:
 
=={{header|Arturo}}==
<langsyntaxhighlight lang="rebol">nPowers: [1 2 4 8 16 32 64 128 256 512]
fermatSet: map 0..9 'x -> 1 + 2 ^ nPowers\[x]
Line 35:
 
loop 0..9 'i ->
print ["Prime factors of F(" i ") =" factors.prime fermatSet\[i]]</langsyntaxhighlight>
 
=={{header|C}}==
Compile with : <pre>gcc -o fermat fermat.c -lgmp</pre>
<langsyntaxhighlight lang="c">#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
Line 79:
 
return 0;
}</langsyntaxhighlight>
<pre>
F(0) = 3 -> PRIME
Line 98:
Built and tested on macOS 10.15, CPU: 3.2 GHz Intel Core i5.
Execution time is about 12 minutes.
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <vector>
#include <boost/integer/common_factor.hpp>
Line 180:
}
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 214:
This uses the 'factor' function defined in the page Prime Decomposition
http://rosettacode.org/wiki/Prime_decomposition#Common_Lisp
<syntaxhighlight lang="lisp">
<lang Lisp>
(defun fermat-number (n)
"Return the n-th Fermat number"
Line 231:
(cdr acc))
(cons (list d 1) acc)))))))))
</syntaxhighlight>
</lang>
 
{{out}}
Line 260:
https://www.gnu.org/software/coreutils/
https://en.wikipedia.org/wiki/GNU_Core_Utilities
<langsyntaxhighlight lang="ruby">require "big"
 
def factors(n)
Line 273:
puts
puts "Factors for each Fermat Number F0 .. F8."
(0..8).each { |n| puts "F#{n} = #{factors fermat(n)}" }</langsyntaxhighlight>
 
System: Lenovo V570 (2011), I5-2410M, 2.9 GHz, Crystal 0.34
Line 305:
 
=={{header|Factor}}==
<langsyntaxhighlight lang="factor">USING: formatting io kernel lists lists.lazy math math.functions
math.primes.factors sequences ;
 
Line 319:
"Factors of F%c: %[%d, %]%s\n" printf 1 +
] each drop
] 2bi</langsyntaxhighlight>
{{out}}
<pre>
Line 355:
 
The timings are for my Intel Core i7-8565U laptop using Go 1.14.1 on Ubuntu 18.04.
<langsyntaxhighlight lang="go">package main
 
import (
Line 715:
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</langsyntaxhighlight>
 
{{out}}
Line 747:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.Numbers.Primes (primeFactors)
import Data.Bool (bool)
 
Line 782:
showFactors x
| 1 < length x = show x
| otherwise = "(prime)"</langsyntaxhighlight>
{{Out}}
<pre>First 10 Fermats:
Line 839:
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
Line 969:
 
}
</syntaxhighlight>
</lang>
Output includes composite numbers attempted to factor with Pollard rho.
{{out}}
Line 1,017:
 
'''Preliminaries'''
<langsyntaxhighlight 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);
 
Line 1,048:
| until( (. * .) > $n or ($n % . == 0); . + 2)
| . * . > $n
end;</langsyntaxhighlight>
'''Fermat Numbers'''
<langsyntaxhighlight lang="jq">def fermat:
. as $n
| (2 | power( 2 | power($n))) + 1;
Line 1,086:
then "F\($i) : rho-prime", " ... => \(if is_prime then "prime" else "not" end)"
else "F\($i) => \($factors)"
end )</langsyntaxhighlight>
{{out}}
<pre>
Line 1,118:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
fermat(n) = BigInt(2)^(BigInt(2)^n) + 1
Line 1,138:
factorfermats(9, true)
factorfermats(10)
</langsyntaxhighlight>{{out}}
<pre>
Fermat number F(0) is 3.
Line 1,162:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">import java.math.BigInteger
import kotlin.math.pow
 
Line 1,283:
private fun pollardRhoG(x: BigInteger, n: BigInteger): BigInteger {
return (x * x + BigInteger.ONE).mod(n)
}</langsyntaxhighlight>
 
=={{header|langur}}==
{{trans|Python}}
{{works with|langur|0.10}}
<langsyntaxhighlight lang="langur">val .fermat = f 2 ^ 2 ^ .n + 1
 
val .factors = f(var .x) {
Line 1,316:
}
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,343:
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[Fermat]
Fermat[n_] := 2^(2^n) + 1
Fermat /@ Range[0, 9]
Scan[FactorInteger /* Print, %]</langsyntaxhighlight>
{{out}}
<pre>{3,5,17,257,65537,4294967297,18446744073709551617,340282366920938463463374607431768211457,115792089237316195423570985008687907853269984665640564039457584007913129639937,13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097}
Line 1,363:
{{trans|Kotlin}}
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import math
import bignum
import strformat
Line 1,474:
echo "First 12 Fermat numbers factored:"
for i in 0..12:
echo fmt"F{subscript(i)} = {factors(i, fermat(i))}"</langsyntaxhighlight>
 
{{out}}
Line 1,519:
{{libheader|ntheory}}
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 1,535:
for my $f (map { [factor($_)] } @Fermats[0..8]) {
printf "Factors of F%s: %s\n", $sub++, @$f == 1 ? 'prime' : join ' ', @$f
}</langsyntaxhighlight>
{{out}}
<pre>First 10 Fermat numbers:
Line 1,562:
=={{header|Phix}}==
{{libheader|Phix/mpfr}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
Note that mpz_prime_factors(), a phix-specific extension to gmp, is designed to find small factors quickly and
Line 1,672:
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(seed (in "/dev/urandom" (rd 8)))
(de **Mod (X Y N)
(let M 1
Line 1,771:
N
':
(if (isprime N) 'PRIME (factors N)) ) ) )</langsyntaxhighlight>
{{out}}
<pre>
Line 1,798:
=={{header|Python}}==
===Procedural===
<langsyntaxhighlight lang="python">def factors(x):
factors = []
i = 2
Line 1,823:
print("F{} -> IS PRIME".format(chr(i + 0x2080)))
else:
print("F{} -> FACTORS: {}".format(chr(i + 0x2080), fac))</langsyntaxhighlight>
{{out}}
<pre>
Line 1,853:
===Functional===
{{Works with|Python|3.7}}
<langsyntaxhighlight lang="python">'''Fermat numbers'''
 
from itertools import count, islice
Line 1,989:
# MAIN ---
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{Out}}
<pre>First ten Fermat numbers:
Line 2,017:
I gave up on factoring F₉ after about 20 minutes.
{{libheader|ntheory}}
<syntaxhighlight lang="raku" perl6line>use ntheory:from<Perl5> <factor>;
 
my @Fermats = (^Inf).map: 2 ** 2 ** * + 1;
Line 2,029:
for @Fermats[^9].map( {"$_".&factor} ) -> $f {
printf "Factors of F%s: %s %s\n", $sub++, $f.join(' '), $f.elems == 1 ?? '- prime' !! ''
}</langsyntaxhighlight>
{{out}}
<pre>First 10 Fermat numbers:
Line 2,057:
=={{header|REXX}}==
=== factoring by trial division ===
<langsyntaxhighlight lang="rexx">/*REXX program to find and display Fermat numbers, and show factors of Fermat numbers.*/
parse arg n . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 9 /*Not specified? Then use the default.*/
Line 2,089:
return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
build: do while z//j==0; z= z % j; ?= ? j; end; return strip(?)</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 2,127:
 
=== factoring via Pollard's rho algorithm ===
<langsyntaxhighlight lang="rexx">/*REXX program to find and display Fermat numbers, and show factors of Fermat numbers.*/
parse arg n . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 9 /*Not specified? Then use the default.*/
Line 2,162:
end /*while*/
end /*x*/
return d /*found a factor of N. Return it.*/</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 2,188:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
decimals(0)
load "stdlib.ring"
Line 2,210:
 
see "done..." + nl
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,232:
https://www.gnu.org/software/coreutils/
https://en.wikipedia.org/wiki/GNU_Core_Utilities
<langsyntaxhighlight lang="ruby">def factors(n)
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:
puts
puts "Factors for each Fermat Number F0 .. F8."
(0..8).each { |n| puts "F#{n} = #{factors fermat(n)}" }</langsyntaxhighlight>
 
System: Lenovo V570 (2011), I5-2410M, 2.9 GHz, Ruby 2.7.1
Line 2,275:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust"> struct DivisorGen {
curr: u64,
last: u64,
Line 2,331:
println!("{} is{}prime", f, not_or_not);
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,348:
===Alternative using rug crate===
Based on the C++ code, which was based on the Java solution.
<langsyntaxhighlight lang="rust">// [dependencies]
// rug = "1.9"
 
Line 2,425:
println!();
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,455:
=={{header|Scala}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="scala">import scala.collection.mutable
import scala.collection.mutable.ListBuffer
 
Line 2,560:
 
def pollardRhoG(x: BigInt, n: BigInt): BigInt = ((x * x) + 1) % n
}</langsyntaxhighlight>
{{out}}
<pre>First 10 Fermat numbers:
Line 2,602:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func fermat_number(n) {
2**(2**n) + 1
}
Line 2,620:
say ("F_#{n} = ", join(' * ', f.shift,
f.map { <C P>[.is_prime] + .len }...))
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,651:
 
=={{header|Tcl}}==
<langsyntaxhighlight lang="tcl">namespace import ::tcl::mathop::*
package require math::numtheory 1.1.1; # Buggy before tcllib-1.20
 
Line 2,673:
puts "factors: $factors"
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,700:
{{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.
<langsyntaxhighlight lang="ecmascript">import "/big" for BigInt
 
var fermat = Fn.new { |n| BigInt.two.pow(2.pow(n)) + 1 }
Line 2,723:
System.print()
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,755:
 
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.
<langsyntaxhighlight lang="ecmascript">/* fermat_numbers_gmp.wren */
 
import "./gmp" for Mpz
Line 2,784:
}
 
System.print("\nThe first factor of F₉ is %(Mpz.pollardRho(fns[9])).")</langsyntaxhighlight>
 
{{out}}
Line 2,816:
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
for big ints and primes
<langsyntaxhighlight lang="zkl">fermatsW:=[0..].tweak(fcn(n){ BI(2).pow(BI(2).pow(n)) + 1 });
println("First 10 Fermat numbers:");
foreach n in (10){ println("F",n,": ",fermatsW.next()) }</langsyntaxhighlight>
{{out}}
<pre style="font-size:83%">
Line 2,833:
F9: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
</pre>
<langsyntaxhighlight lang="zkl">fcn primeFactorsBI(n){ // Return a list of the prime factors of n
acc:=fcn(n,k,acc,maxD){ // k is primes
if(n==1 or k>maxD) acc.close();
Line 2,845:
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fermatsW:=[0..].tweak(fcn(n){ BI(2).pow(BI(2).pow(n)) + 1 });
println("Factors of first few Fermat numbers:");
foreach n in (7){
println("Factors of F",n,": ",factorsBI(fermatsW.next()).concat(" "));
}</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327533"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information