Fermat numbers: Difference between revisions

 

In mathematics, a Fermat number, ''named after Pierre de Fermat who first studied them,'' is a positive integer of the form <big>'''F_n = 2^{''2''^''n''} + 1'''</big> where '''n''' is a non-negative integer.

<br>

 

 

 

 

 

 

{{out}}

 

 

 

=={{header|C}}==

Compile with : <pre>gcc -o fermat fermat.c -lgmp</pre>

#include <stdio.h>

#include <gmp.h>

 

return 0;

<pre>

F(0) = 3 -> PRIME

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>

}

return 0;

 

{{out}}

</pre>

 

{{trans|Ruby}}

This uses the `factor` function from the `coreutils` library

https://www.gnu.org/software/coreutils/

https://en.wikipedia.org/wiki/GNU_Core_Utilities

 

def factors(n)

puts

puts "Factors for each Fermat Number F0 .. F8."

 

System: Lenovo V570 (2011), I5-2410M, 2.9 GHz, Crystal 0.34

 

=={{header|Factor}}==

math.primes.factors sequences ;

 

"Factors of F%c: %[%d, %]%s\n" printf 1 +

] each drop

{{out}}

<pre>

 

The timings are for my Intel Core i7-8565U laptop using Go 1.14.1 on Ubuntu 18.04.

 

import (

}

fmt.Printf("\nTook %s\n", time.Since(start))

 

{{out}}

 

=={{header|Haskell}}==

import Data.Bool (bool)

fermat :: Integer -> Integer

fermat = succ . (2 ^) . (2 ^)

fermats :: [Integer]

fermats = fermat <$> [0 ..]

main :: IO ()

main =

"Factors of first 7:"

show

primeFactors

(take 7 fermats)

]

fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String

fTable s xShow fxShow f xs =

where

rjust n c = drop . length <*> (replicate n c ++)

{{Out}}

<pre>First 10 Fermats:

 

=={{header|Java}}==

import java.math.BigInteger;

import java.util.ArrayList;

 

}

Output includes composite numbers attempted to factor with Pollard rho.

{{out}}

F[12] = 114689 * 26017793 * 63766529 * (C1213)

</pre>

 

=={{header|Julia}}==

 

fermat(n) = BigInt(2)^(BigInt(2)^n) + 1

factorfermats(9, true)

factorfermats(10)

<pre>

Fermat number F(0) is 3.

=={{header|Kotlin}}==

{{trans|Java}}

import kotlin.math.pow

 

private fun pollardRhoG(x: BigInteger, n: BigInteger): BigInteger {

return (x * x + BigInteger.ONE).mod(n)

 

=={{header|langur}}==

{{trans|Python}}

 

if .x div .i {

.f ~= [.i]

.x \= .i

}

} ~ [.x]

}

}

 

{{out}}

<pre>first 10 Fermat numbers

F₀ = 3

F₅ factors: [641, 6700417]

F₆ factors: [274177, 67280421310721]

</pre>

 

{{libheader|ntheory}}

{{trans|Raku}}

use warnings;

use feature 'say';

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:

=={{header|Phix}}==

{{libheader|Phix/mpfr}}

{{out}}

Note that mpz_prime_factors(), a phix-specific extension to gmp, is designed to find small factors quickly and

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|Python}}==

===Procedural===

factors = []

i = 2

print("F{} -> IS PRIME".format(chr(i + 0x2080)))

else:

{{out}}

<pre>

===Functional===

{{Works with|Python|3.7}}

 

from itertools import count, islice

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>First ten Fermat numbers:

=={{header|Raku}}==

(formerly Perl 6)

 

 

my @Fermats = (^Inf).map: 2 ** 2 ** * + 1;

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:

=={{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.*/

return ?

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=== 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.*/

numeric digits 200 /*ensure enough decimal digits, for n=9*/

 

say

/*──────────────────────────────────────────────────────────────────────────────────────*/

commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _

/*──────────────────────────────────────────────────────────────────────────────────────*/

rho: procedure; parse arg n; y= 2; d= 1 /*initialize X, Y, and D variables.*/

x= (x*x + 1) // n

v= (y*y + 1) // n

d= xy /*assign variable D with a new XY */

end /*while*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

</pre>

 

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

puts

puts "Factors for each Fermat Number F0 .. F8."

 

System: Lenovo V570 (2011), I5-2410M, 2.9 GHz, Ruby 2.7.1

 

=={{header|Rust}}==

curr: u64,

last: u64,

println!("{} is{}prime", f, not_or_not);

}

{{out}}

<pre>

===Alternative using rug crate===

Based on the C++ code, which was based on the Java solution.

// rug = "1.9"

 

println!();

}

 

{{out}}

F(8): 1238926361552897, 93461639715357977769163558199606896584051237541638188580280321

</pre>

 

=={{header|Sidef}}==

2**(2**n) + 1

}

say ("F_#{n} = ", join(' * ', f.shift,

f.map { <C P>[.is_prime] + .len }...))

{{out}}

<pre>

F_12 = 114689 * C1228

F_13 = 2710954639361 * C2454

</pre>

 

=={{header|Wren}}==

 

 

 

{{out}}

<pre>

</pre>

 

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library

for big ints and primes

println("First 10 Fermat numbers:");

{{out}}

<pre style="font-size:83%">

F9: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097

</pre>

acc:=fcn(n,k,acc,maxD){ // k is primes

if(n==1 or k>maxD) acc.close();

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>