First 9 prime Fibonacci number: Difference between revisions
Ada version |
m Ada: Fix Is_Prime |
||
Line 17: | Line 17: | ||
if A mod 3 = 0 then return False; end if; |
if A mod 3 = 0 then return False; end if; |
||
D := 5; |
D := 5; |
||
while D * D < A loop |
while D * D <= A loop |
||
if A mod D = 0 then |
if A mod D = 0 then |
||
return False; |
return False; |
Revision as of 11:36, 12 July 2022
- Task
Show on this page the first 9 prime Fibonacci numbers.
Ada
<lang Ada>with Ada.Text_IO;
procedure Prime_Fibonacci is
function Is_Prime (A : Natural) return Boolean is D : Natural; begin if A < 2 then return False; end if; if A in 2 .. 3 then return True; end if; if A mod 2 = 0 then return False; end if; if A mod 3 = 0 then return False; end if; D := 5; while D * D <= A loop if A mod D = 0 then return False; end if; D := D + 2; if A mod D = 0 then return False; end if; D := D + 4; end loop; return True; end Is_Prime;
F_1 : Natural := 0; F_2 : Natural := 1;
function Fibonacci return Natural is R : Natural := F_1 + F_2; begin F_1 := F_2; F_2 := R; return R; end Fibonacci;
Count : Natural := 0; Fib : Natural;
begin
while Count < 9 loop Fib := Fibonacci; if Is_Prime (Fib) then Count := Count + 1; Ada.Text_IO.Put_Line (Fib'Image); end if; end loop;
end Prime_Fibonacci;</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
ALGOL 68
<lang algol68>BEGIN # show the first 9 prime fibonacci numbers #
PR read "primes.incl.a68" PR # include prime utilities # INT p count := 0; INT prev := 0; INT curr := 1; WHILE p count < 9 DO INT next = prev + curr; prev := curr; curr := next; IF is probably prime( curr ) THEN # have a prime fibonacci number # p count +:= 1; print( ( " ", whole( curr, 0 ) ) ) FI OD
END</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
AWK
<lang AWK>
- syntax: GAWK -f FIRST_9_PRIME_FIBONACCI_NUMBER.AWK
BEGIN {
f1 = f2 = 1 stop = 9 printf("First %d Prime Fibonacci numbers:\n",stop) while (count < stop) { f3 = f1 + f2 if (is_prime(f3)) { printf("%d ",f3) count++ } f1 = f2 f2 = f3 } printf("\n") exit(0)
} function is_prime(n, d) {
d = 5 if (n < 2) { return(0) } if (n % 2 == 0) { return(n == 2) } if (n % 3 == 0) { return(n == 3) } while (d*d <= n) { if (n % d == 0) { return(0) } d += 2 if (n % d == 0) { return(0) } d += 4 } return(1)
} </lang>
- Output:
First 9 Prime Fibonacci numbers: 2 3 5 13 89 233 1597 28657 514229
BASIC
BASIC256
<lang BASIC256>function isPrime(v) if v < 2 then return False if v mod 2 = 0 then return v = 2 if v mod 3 = 0 then return v = 3 d = 5 while d * d <= v if v mod d = 0 then return False else d += 2 end while return True end function
function fib(nr) if nr = 0 then return 0 if nr = 1 then return 1 if nr > 1 then return fib(nr-1) + fib(nr-2) end function
i = 0 cont = 0 print "The first 9 Prime Fibonacci numbers: " while True i += 1 num = fib(i) if isPrime(num) then cont += 1 if cont < 10 then print num; " "; else exit while end if end if end while end</lang>
- Output:
Igual que la entrada de FreeBASIC.
FreeBASIC
<lang freebasic>Function isPrime(Byval ValorEval As Integer) As Boolean
If ValorEval <= 1 Then Return False For i As Integer = 2 To Int(Sqr(ValorEval)) If ValorEval Mod i = 0 Then Return False Next i Return True
End Function
Function fib(nr As Integer) As Integer
If nr = 0 Then Return 0 If nr = 1 Then Return 1 If nr > 1 Then Return fib(nr-1) + fib(nr-2)
End Function
Dim As Integer i = 0, num, cont = 0 Print "The first 9 Prime Fibonacci numbers: " Do
i += 1 num = fib(i) If isprime(num) Then cont += 1 If cont < 10 Then Print num; " "; Else Exit Do End If End If
Loop Sleep</lang>
- Output:
The first 9 Prime Fibonacci numbers: 2 3 5 13 89 233 1597 28657 514229
PureBasic
<lang PureBasic>Procedure isPrime(v.i)
If v <= 1 : ProcedureReturn #False ElseIf v < 4 : ProcedureReturn #True ElseIf v % 2 = 0 : ProcedureReturn #False ElseIf v < 9 : ProcedureReturn #True ElseIf v % 3 = 0 : ProcedureReturn #False Else Protected r = Round(Sqr(v), #PB_Round_Down) Protected f = 5 While f <= r If v % f = 0 Or v % (f + 2) = 0 ProcedureReturn #False EndIf f + 6 Wend EndIf ProcedureReturn #True
EndProcedure
Procedure fib(nr.i)
If nr = 0 : ProcedureReturn 0 ElseIf nr = 1 : ProcedureReturn 1 ElseIf nr > 1 : ProcedureReturn fib(nr-1) + fib(nr-2) EndIf
EndProcedure
If OpenConsole()
Define i.i = 0, cont.i = 0 PrintN("The first 9 Prime Fibonacci numbers: ") Repeat i + 1 num = fib(i) If isprime(num) cont + 1 If cont < 10 Print(Str(num) + " ") Else Break EndIf EndIf ForEver PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input() CloseConsole()
EndIf</lang>
- Output:
Igual que la entrada de FreeBASIC.
Yabasic
<lang yabasic>sub isPrime(v)
if v < 2 then return False : fi if mod(v, 2) = 0 then return v = 2 : fi if mod(v, 3) = 0 then return v = 3 : fi d = 5 while d * d <= v if mod(v, d) = 0 then return False else d = d + 2 : fi wend return True
end sub
sub fib(nr)
if nr = 0 then return 0 : fi if nr = 1 then return 1 : fi if nr > 1 then return fib(nr-1) + fib(nr-2) : fi
end sub
i = 0 cont = 0 print "The first 9 Prime Fibonacci numbers: " do
i = i + 1 num = fib(i) if isPrime(num) then cont = cont + 1 if cont < 10 then print num, " "; else break end if end if
loop end</lang>
- Output:
Igual que la entrada de FreeBASIC.
C
Requires C99 or later. <lang c>#include <stdio.h>
- include <stdint.h>
- include <stdbool.h>
bool isPrime(uint64_t n) {
if (n < 2) return false; if (!(n%2)) return n == 2; if (!(n%3)) return n == 3; uint64_t d = 5; while (d*d <= n) { if (!(n%d)) return false; d += 2; if (!(n%d)) return false; d += 4; } return true;
}
int main() {
uint64_t f1 = 1, f2 = 1, f3; int count = 0, limit = 12; // as far as we can get without using GMP printf("The first %d prime Fibonacci numbers are:\n", limit); while (count < limit) { f3 = f1 + f2; if (isPrime(f3)) { printf("%ld ", f3); count++; } f1 = f2; f2 = f3; } printf("\n"); return 0;
}</lang>
- Output:
The first 12 prime Fibonacci numbers are: 2 3 5 13 89 233 1597 28657 514229 433494437 2971215073 99194853094755497
C++
<lang cpp>#include <chrono>
- include <iostream>
- include <sstream>
- include <utility>
- include <primesieve.hpp>
- include <gmpxx.h>
using big_int = mpz_class;
bool is_probably_prime(const big_int& n) {
return mpz_probab_prime_p(n.get_mpz_t(), 30) != 0;
}
class prime_fibonacci_generator { public:
prime_fibonacci_generator(); std::pair<uint64_t, big_int> next();
private:
big_int next_fibonacci(); primesieve::iterator p_; big_int f0_ = 0; big_int f1_ = 1; uint64_t n_ = 0;
};
prime_fibonacci_generator::prime_fibonacci_generator() {
for (int i = 0; i < 2; ++i) p_.next_prime();
}
std::pair<uint64_t, big_int> prime_fibonacci_generator::next() {
for (;;) { if (n_ > 4) { uint64_t p = p_.next_prime(); for (; p > n_; ++n_) next_fibonacci(); } ++n_; big_int f = next_fibonacci(); if (is_probably_prime(f)) return {n_ - 1, f}; }
}
big_int prime_fibonacci_generator::next_fibonacci() {
big_int result = f0_; big_int f = f0_ + f1_; f0_ = f1_; f1_ = f; return result;
}
std::string to_string(const big_int& n) {
std::string str = n.get_str(); if (str.size() > 40) { std::ostringstream os; os << str.substr(0, 20) << "..." << str.substr(str.size() - 20) << " (" << str.size() << " digits)"; return os.str(); } return str;
}
int main() {
auto start = std::chrono::high_resolution_clock::now(); prime_fibonacci_generator gen; for (int i = 1; i <= 26; ++i) { auto [n, f] = gen.next(); std::cout << i << ": F(" << n << ") = " << to_string(f) << '\n'; } auto finish = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> ms(finish - start); std::cout << "elapsed time: " << ms.count() << " seconds\n";
}</lang>
- Output:
1: F(3) = 2 2: F(4) = 3 3: F(5) = 5 4: F(7) = 13 5: F(11) = 89 6: F(13) = 233 7: F(17) = 1597 8: F(23) = 28657 9: F(29) = 514229 10: F(43) = 433494437 11: F(47) = 2971215073 12: F(83) = 99194853094755497 13: F(131) = 1066340417491710595814572169 14: F(137) = 19134702400093278081449423917 15: F(359) = 47542043773469822074...62268716376935476241 (75 digits) 16: F(431) = 52989271100609562179...55134424689676262369 (90 digits) 17: F(433) = 13872771278047838271...25954602593712568353 (91 digits) 18: F(449) = 30617199924845450305...49015933442805665949 (94 digits) 19: F(509) = 10597999265301490732...54396195769876129909 (107 digits) 20: F(569) = 36684474316080978061...15228143777781065869 (119 digits) 21: F(571) = 96041200618922553823...31637646183008074629 (119 digits) 22: F(2971) = 35710356064190986072...48642001438470316229 (621 digits) 23: F(4723) = 50019563612695729290...02854387700053591957 (987 digits) 24: F(5387) = 29304412869392580554...82040327194725855833 (1126 digits) 25: F(9311) = 34232086066590238613...37580645424669476289 (1946 digits) 26: F(9677) = 10565977873308861656...95169792504550670357 (2023 digits) elapsed time: 21.8042 seconds
CLU
<lang clu>fibonacci = iter () yields (int)
a: int := 1 b: int := 1 while true do yield(a) a, b := b, a+b end
end fibonacci
prime = proc (n: int) returns (bool)
if n <= 4 then return(n=2 cor n=3) end if n//2=0 cor n//3=0 then return(false) end d: int := 5 while d*d <= n do if n//d=0 then return(false) end d := d+2 if n//d=0 then return(false) end d := d+4 end return(true)
end prime
start_up = proc ()
po: stream := stream$primary_output() seen: int := 0 for n: int in fibonacci() do if seen=9 then break end if prime(n) then stream$putl(po, int$unparse(n)) seen := seen+1 end end
end start_up</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
COBOL
<lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. PRIME-FIBONACCI. DATA DIVISION. WORKING-STORAGE SECTION. 01 FIBONACCI-VARS. 03 FIB PIC 9(6). 03 FIB-B PIC 9(6). 03 FIB-C PIC 9(6). 03 FIB-OUT PIC Z(5)9. 01 PRIME-VARS. 03 PRIME-FLAG PIC X. 88 PRIME VALUE 'X'. 03 DSOR PIC 9(4). 03 DSOR-SQ PIC 9(6). 03 DIV-RSLT PIC 9(6)V9(3). 03 FILLER REDEFINES DIV-RSLT. 05 FILLER PIC 9(6). 05 FILLER PIC 9(3). 88 DIVISIBLE VALUE ZERO. PROCEDURE DIVISION. BEGIN. MOVE 1 TO FIB, FIB-B. PERFORM FIND-PRIME-FIBONACCI 9 TIMES. STOP RUN. FIND-PRIME-FIBONACCI. ADD FIB, FIB-B GIVING FIB-C. MOVE FIB-B TO FIB. MOVE FIB-C TO FIB-B. PERFORM CHECK-PRIME. IF NOT PRIME, GO TO FIND-PRIME-FIBONACCI. MOVE FIB TO FIB-OUT. DISPLAY FIB-OUT. CHECK-PRIME SECTION. BEGIN. MOVE SPACE TO PRIME-FLAG. IF FIB IS LESS THAN 5, GO TO TRIVIAL-PRIME. DIVIDE FIB BY 2 GIVING DIV-RSLT. IF DIVISIBLE, GO TO DONE. DIVIDE FIB BY 3 GIVING DIV-RSLT. IF DIVISIBLE, GO TO DONE. MOVE 5 TO DSOR. MOVE 25 TO DSOR-SQ. MOVE 'X' TO PRIME-FLAG. PERFORM TEST-DIVISOR UNTIL NOT PRIME OR DSOR-SQ IS GREATER THAN FIB. GO TO DONE. TEST-DIVISOR. DIVIDE FIB BY DSOR GIVING DIV-RSLT. IF DIVISIBLE, MOVE SPACE TO PRIME-FLAG. ADD 2 TO DSOR. DIVIDE FIB BY DSOR GIVING DIV-RSLT. IF DIVISIBLE, MOVE SPACE TO PRIME-FLAG. ADD 4 TO DSOR. MULTIPLY DSOR BY DSOR GIVING DSOR-SQ. TRIVIAL-PRIME. IF FIB IS EQUAL TO 2 OR 3, MOVE 'X' TO PRIME-FLAG. DONE. EXIT.</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
Comal
<lang comal>0010 FUNC prime(n) CLOSED 0020 IF n<4 THEN RETURN n=2 OR n=3 0030 IF n MOD 2=0 OR n MOD 3=0 THEN RETURN FALSE 0040 d:=5 0050 WHILE d*d<=n DO 0060 IF n MOD d=0 THEN RETURN FALSE 0070 d:+2 0080 IF n MOD d=0 THEN RETURN FALSE 0090 d:+4 0100 ENDWHILE 0110 RETURN TRUE 0120 ENDFUNC prime 0130 // 0140 found:=0 0150 a:=1;b:=1 0160 WHILE found<9 DO 0170 IF prime(a) THEN 0180 PRINT a 0190 found:+1 0200 ENDIF 0210 c:=a+b;a:=b;b:=c 0220 ENDWHILE 0230 END</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
Cowgol
<lang cowgol>include "cowgol.coh";
sub prime(n: uint32): (p: uint8) is
p := 0; if n <= 4 then if n==2 or n==3 then p := 1; end if; elseif n&1 != 0 and n%3 != 0 then var d: uint32 := 5; while d*d <= n loop if n%d == 0 then return; end if; d := d + 2; if n%d == 0 then return; end if; d := d + 4; end loop; p := 1; end if;
end sub;
var a: uint32 := 1; var b: uint32 := 1; var n: uint8 := 0;
while n<9 loop
if prime(a) != 0 then print_i32(a); print_nl(); n := n+1; end if; var c := a + b; a := b; b := c;
end loop;</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
Draco
<lang draco>proc nonrec prime(ulong n) bool:
bool comp; ulong d; if n <= 4 then n=2 or n=3 elif n&1 = 0 or n%3 = 0 then false else d := 5; comp := false; while not comp and d*d <= n do if n%d = 0 then comp := true fi; d := d + 2; if n%d = 0 then comp := true fi; d := d + 4 od; not comp fi
corp
proc nonrec main() void:
ulong a, b, c; byte n; a := 1; b := 1; n := 0; while n < 9 do if prime(a) then writeln(a); n := n + 1 fi; c := a + b; a := b; b := c od
corp</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
F#
<lang fsharp> // Prime Fibonacci Numbers. Nigel Galloway: January 21st., 2022 seq{yield! [2I;3I]; yield! MathNet.Numerics.Generate.FibonacciSequence()|>Seq.skip 5|>Seq.filter(fun n->n%4I=1I && Open.Numeric.Primes.MillerRabin.IsProbablePrime &n)}|>Seq.take 23|>Seq.iteri(fun n g->printfn "%2d->%A" (n+1) g) </lang>
- Output:
1->2 2->3 3->5 4->13 5->89 6->233 7->1597 8->28657 9->514229 10->433494437 11->2971215073 12->99194853094755497 13->1066340417491710595814572169 14->19134702400093278081449423917 15->475420437734698220747368027166749382927701417016557193662268716376935476241 16->529892711006095621792039556787784670197112759029534506620905162834769955134424689676262369 17->1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353 18->3061719992484545030554313848083717208111285432353738497131674799321571238149015933442805665949 19->10597999265301490732599643671505003412515860435409421932560009680142974347195483140293254396195769876129909 20->36684474316080978061473613646275630451100586901195229815270242868417768061193560857904335017879540515228143777781065869 21->96041200618922553823942883360924865026104917411877067816822264789029014378308478864192589084185254331637646183008074629 22->357103560641909860720907774139063454445569926582843306794041997476301071102767570483343563518510007800304195444080518562630900027386498933944619210192856768352683468831754423234217978525765921040747291316681576556861490773135214861782877716560879686368266117365351884926393775431925116896322341130075880287169244980698837941931247516010101631704349963583400361910809925847721300802741705519412306522941202429437928826033885416656967971559902743150263252229456298992263008126719589203430407385228230361628494860172129702271172926469500802342608722006420745586297267929052509059154340968348509580552307148642001438470316229 23->500195636126957292905024512596972806695803345136243348970565288179435361313804956505581782637634612477979679893275103396147348650762007594937510804541145002304302867341006298493404319657382123201158007188252606550806694535329232256851056656372379649097735304781630173812454531781511107460619516018844320335033801984806819067802561370394036732654089838823551603083295670024453477589093119918386566397677610274213837391954591147603054442650326827980781140275941425217172428448698161710841740688042587204161256084914166762549007012713922172748259690566614580062682196606466498102571627683726718483229578044343646737694436406261444368327649097401550241341102704783841619376027737767077127010039900586625841991295111482539736725172169379740443890332234341104310470907449898415522414805210341138063350999730749950920147250683227798780264811215647706542511681027825390882770762662185410080310045261286851842669934849330548237271838345164232560544964315090365421726004108704302854387700053591957
Factor
<lang factor>USING: kernel lists lists.lazy math.primes prettyprint sequences ;
- prime-fib ( -- list )
{ 0 1 } [ [ rest ] [ sum suffix ] bi ] lfrom-by [ second ] lmap-lazy [ prime? ] lfilter ;
9 prime-fib ltake [ . ] leach</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
Go
<lang go>package main
import "fmt"
func isPrime(n uint64) bool {
if n < 2 { return false } if n%2 == 0 { return n == 2 } if n%3 == 0 { return n == 3 } d := uint64(5) for d*d <= n { if n%d == 0 { return false } d += 2 if n%d == 0 { return false } d += 4 } return true
}
func main() {
f1 := uint64(1) f2 := f1 count := 0 limit := 12 // as far as we can get without using big.Int fmt.Printf("The first %d prime Fibonacci numbers are:\n", limit) for count < limit { f3 := f1 + f2 if isPrime(f3) { fmt.Printf("%d ", f3) count++ } f1 = f2 f2 = f3 } fmt.Println()
}</lang>
- Output:
The first 12 prime Fibonacci numbers are: 2 3 5 13 89 233 1597 28657 514229 433494437 2971215073 99194853094755497
J
Here, we pick a convenient expression and generate fibonacci numbers
<lang J>fib=: <. 0.5 + (%:5) %~ (2 %~ 1+%:5)^i.63</lang>
Then we select the first 9 which are prime:
<lang J> 9 {. (#~ 1&p:) fib 2 3 5 13 89 233 1597 28657 514229</lang>
jq
Works with jq (*)
Works with gojq, the Go implementation of jq
See Erdős-primes#jq for a suitable definition of `is_prime` as used here.
(*) For unlimited precision integer arithmetic, use gojq. <lang jq># Emit an unbounded stream of Fibonacci numbers def fibonaccis:
# input: [f(i-2), f(i-1)] def fib: (.[0] + .[1]) as $sum | if .[2] == 0 then $sum else $sum, ([ .[1], $sum ] | fib) end; [-1, 1] | fib;
"The first 9 prime Fibonacci numbers are:", limit(9; fibonaccis | select(is_prime))</lang>
- Output:
The first 9 prime Fibonacci numbers are: 2 3 5 13 89 233 1597 28657 514229
Java
Uses the PrimeGenerator class from Extensible prime generator#Java. <lang java>import java.math.BigInteger;
public class PrimeFibonacciGenerator {
private PrimeGenerator primeGen = new PrimeGenerator(10000, 200000); private BigInteger f0 = BigInteger.ZERO; private BigInteger f1 = BigInteger.ONE; private int index = 0;
public static void main(String[] args) { PrimeFibonacciGenerator gen = new PrimeFibonacciGenerator(); long start = System.currentTimeMillis(); for (int i = 1; i <= 26; ++i) { BigInteger f = gen.next(); System.out.printf("%d: F(%d) = %s\n", i, gen.index - 1, toString(f)); } long finish = System.currentTimeMillis(); System.out.printf("elapsed time: %g seconds\n", (finish - start)/1000.0); }
private PrimeFibonacciGenerator() { for (int i = 0; i < 2; ++i) primeGen.nextPrime(); }
private BigInteger next() { for (;;) { if (index > 4) { int p = primeGen.nextPrime(); for (; p > index; ++index) nextFibonacci(); } ++index; BigInteger f = nextFibonacci(); if (f.isProbablePrime(30)) return f; } }
private BigInteger nextFibonacci() { BigInteger result = f0; BigInteger f = f0.add(f1); f0 = f1; f1 = f; return result; }
private static String toString(BigInteger f) { String str = f.toString(); if (str.length() > 40) { StringBuilder s = new StringBuilder(str.substring(0, 20)); s.append("..."); s.append(str.substring(str.length() - 20)); s.append(" ("); s.append(str.length()); s.append(" digits)"); str = s.toString(); } return str; }
}</lang>
- Output:
1: F(3) = 2 2: F(4) = 3 3: F(5) = 5 4: F(7) = 13 5: F(11) = 89 6: F(13) = 233 7: F(17) = 1597 8: F(23) = 28657 9: F(29) = 514229 10: F(43) = 433494437 11: F(47) = 2971215073 12: F(83) = 99194853094755497 13: F(131) = 1066340417491710595814572169 14: F(137) = 19134702400093278081449423917 15: F(359) = 47542043773469822074...62268716376935476241 (75 digits) 16: F(431) = 52989271100609562179...55134424689676262369 (90 digits) 17: F(433) = 13872771278047838271...25954602593712568353 (91 digits) 18: F(449) = 30617199924845450305...49015933442805665949 (94 digits) 19: F(509) = 10597999265301490732...54396195769876129909 (107 digits) 20: F(569) = 36684474316080978061...15228143777781065869 (119 digits) 21: F(571) = 96041200618922553823...31637646183008074629 (119 digits) 22: F(2971) = 35710356064190986072...48642001438470316229 (621 digits) 23: F(4723) = 50019563612695729290...02854387700053591957 (987 digits) 24: F(5387) = 29304412869392580554...82040327194725855833 (1126 digits) 25: F(9311) = 34232086066590238613...37580645424669476289 (1946 digits) 26: F(9677) = 10565977873308861656...95169792504550670357 (2023 digits) elapsed time: 53.7480 seconds
Julia
<lang julia>using Lazy using Primes
fibs = @lazy big"0":big"1":(fibs + drop(1, fibs))
primefibs = @>> fibs filter(isprime)
println(take(9, primefibs)) # List: (2 3 5 13 89 233 1597 28657 514229) </lang>
Mathematica /Wolfram Language
First solution by guessing some upper bound: <lang Mathematica>Select[Fibonacci /@ Range[100], PrimeQ, 9]</lang>
- Output:
{2, 3, 5, 13, 89, 233, 1597, 28657, 514229}
Second solution without guessing some upper bound: <lang Mathematica>list = {}; Do[
f = Fibonacci[i]; If[PrimeQ[f], AppendTo[list, {i, f}]; If[Length[list] >= 26, Break[]] ] , {i, 1, \[Infinity]} ];
out=Row[{"F(",#1,") = ",If[IntegerLength[#2]<=10,#2,Row@Catenate[{Take[IntegerDigits[#2],5],{" \[Ellipsis] "},Take[IntegerDigits[#2],-5],{" (",IntegerLength[#2]," digits)"}}]]}]&@@@list; TableForm[out,TableHeadings->{Automatic,None}]</lang>
- Output:
1 F(3) = 2 2 F(4) = 3 3 F(5) = 5 4 F(7) = 13 5 F(11) = 89 6 F(13) = 233 7 F(17) = 1597 8 F(23) = 28657 9 F(29) = 514229 10 F(43) = 433494437 11 F(47) = 2971215073 12 F(83) = 99194 … 55497 (17 digits) 13 F(131) = 10663 … 72169 (28 digits) 14 F(137) = 19134 … 23917 (29 digits) 15 F(359) = 47542 … 76241 (75 digits) 16 F(431) = 52989 … 62369 (90 digits) 17 F(433) = 13872 … 68353 (91 digits) 18 F(449) = 30617 … 65949 (94 digits) 19 F(509) = 10597 … 29909 (107 digits) 20 F(569) = 36684 … 65869 (119 digits) 21 F(571) = 96041 … 74629 (119 digits) 22 F(2971) = 35710 … 16229 (621 digits) 23 F(4723) = 50019 … 91957 (987 digits) 24 F(5387) = 29304 … 55833 (1126 digits) 25 F(9311) = 34232 … 76289 (1946 digits) 26 F(9677) = 10565 … 70357 (2023 digits)
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/First_9_Prime_Fibonacci_Number use warnings; use ntheory qw( is_prime );
my @first; my $x = my $y = 1; while( @first < 9 )
{ ($x, $y) = ($x + $y, $x); is_prime( $x ) and push @first, $x; }
print "@first\n";</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229
Phix
You can run this online here.
with javascript_semantics include mpfr.e integer n = 1, count=0 mpz f = mpz_init() atom t0 = time(), t1 = time()+1 while count<iff(platform()=JS?21:26) do integer fn = iff(n<4?n+2:get_prime(n)) mpz_fib_ui(f, fn) if mpz_prime(f) then count += 1 string e = elapsed(time()-t0) printf(1,"%2d: fib(%d) = %s (%s)\n",{count,fn,shorten(mpz_get_str(f)),e}) elsif platform()!=JS and time()>t1 then printf(1,"%d\r",fn) t1 = time()+1 end if n += 1 end while
- Output:
1: fib(3) = 2 (0s) 2: fib(4) = 3 (0.1s) 3: fib(5) = 5 (0.2s) 4: fib(7) = 13 (0.2s) 5: fib(11) = 89 (0.2s) 6: fib(13) = 233 (0.2s) 7: fib(17) = 1597 (0.2s) 8: fib(23) = 28657 (0.2s) 9: fib(29) = 514229 (0.2s) 10: fib(43) = 433494437 (0.2s) 11: fib(47) = 2971215073 (0.2s) 12: fib(83) = 99194853094755497 (0.2s) 13: fib(131) = 1066340417491710595814572169 (0.2s) 14: fib(137) = 19134702400093278081449423917 (0.2s) 15: fib(359) = 47542043773469822074...62268716376935476241 (75 digits) (0.2s) 16: fib(431) = 52989271100609562179...55134424689676262369 (90 digits) (0.2s) 17: fib(433) = 13872771278047838271...25954602593712568353 (91 digits) (0.2s) 18: fib(449) = 30617199924845450305...49015933442805665949 (94 digits) (0.2s) 19: fib(509) = 10597999265301490732...54396195769876129909 (107 digits) (0.2s) 20: fib(569) = 36684474316080978061...15228143777781065869 (119 digits) (0.2s) 21: fib(571) = 96041200618922553823...31637646183008074629 (119 digits) (0.2s) 22: fib(2971) = 35710356064190986072...48642001438470316229 (621 digits) (2.8s) 23: fib(4723) = 50019563612695729290...02854387700053591957 (987 digits) (14.0s) 24: fib(5387) = 29304412869392580554...82040327194725855833 (1,126 digits) (22.4s) 25: fib(9311) = 34232086066590238613...37580645424669476289 (1,946 digits) (2 minutes and 38s) 26: fib(9677) = 10565977873308861656...95169792504550670357 (2,023 digits) (3 minutes and 3s)
Pike
<lang Pike>bool isPrime(int n) { if (n < 2) { return false; } if (!(n%2)) { return n == 2; } if (!(n%3)) { return n == 3; }
int d = 5;
while(d*d <= n) { if (!(n%d)) { return false; } d += 2; if (!(n%d)) { return false; } d += 4; } return true; }
int main() { int limit = 12;
write("The first " + (string)limit + " prime Fibonacci numbers are:\n");
int count = 0; int f1, f2; f1 = f2 = 1;
while(count < limit) { int f3 = f2 + f1; if (isPrime(f3)) { write((string)f3 + " "); count = count + 1; } f1 = f2; f2 = f3; } write("\n"); return 0; }</lang>
- Output:
The first 12 prime Fibonacci numbers are: 2 3 5 13 89 233 1597 28657 514229 433494437 2971215073 99194853094755497
Python
<lang python> print("working...") print("The firsr 9 Prime Fibonacci numbers:")
num = 0
def isprime(m):
for i in range(2,int(m**0.5)+1): if m%i==0: return False return True
def fib(nr): if (nr == 0): return 0 if (nr == 1): return 1 if (nr > 1): return fib(nr-1) + fib(nr-2)
for n in range(2,520000): x = fib(n) if isprime(x): num = num + 1 if (x > 1): if (num < 11): print(str(x),end=" ") else: break
print() print("done...") </lang>
- Output:
working... The firsr 9 Prime Fibonacci numbers: 2 3 5 13 89 233 1597 28657 514229 done...
Raku
<lang perl6>put ++$ .fmt("%2d: ") ~ $_ for (0, 1, * + * … *).grep( &is-prime )[^20];</lang>
- Output:
1: 2 2: 3 3: 5 4: 13 5: 89 6: 233 7: 1597 8: 28657 9: 514229 10: 433494437 11: 2971215073 12: 99194853094755497 13: 1066340417491710595814572169 14: 19134702400093278081449423917 15: 475420437734698220747368027166749382927701417016557193662268716376935476241 16: 529892711006095621792039556787784670197112759029534506620905162834769955134424689676262369 17: 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353 18: 3061719992484545030554313848083717208111285432353738497131674799321571238149015933442805665949 19: 10597999265301490732599643671505003412515860435409421932560009680142974347195483140293254396195769876129909 20: 36684474316080978061473613646275630451100586901195229815270242868417768061193560857904335017879540515228143777781065869
Ring
<lang ring> load "stdlibcore.ring" see "working..." + nl num = 0
see "The first 9 Prime Fibonacci numbers: " + nl for n = 1 to 1000000
x = fib(n) if isprime(x) num++ if num< 10 ? "" + x + " " else exit ok ok
next
see "done..." + nl
func fib nr
if nr = 0 return 0 ok if nr = 1 return 1 ok if nr > 1 return fib(nr-1) + fib(nr-2) ok
</lang>
- Output:
working... The first 9 Prime Fibonacci numbers: 2 3 5 13 89 233 1597 28657 514229 done...
Rust
<lang rust>// [dependencies] // rug = "1.15.0" // primal = "0.3"
use rug::{Assign, Integer};
fn fibonacci() -> impl std::iter::Iterator<Item = Integer> {
let mut f0 = Integer::from(0); let mut f1 = Integer::from(1); std::iter::from_fn(move || { let result = Integer::from(&f0); let f = Integer::from(&f0 + &f1); f0.assign(&f1); f1.assign(&f); Some(result) })
}
fn prime_fibonacci() -> impl std::iter::Iterator<Item = (usize, Integer)> {
use rug::integer::IsPrime; let mut primes = primal::Primes::all().skip(2); let mut fib = fibonacci(); let mut n = 0; std::iter::from_fn(move || loop { if n > 4 { let p = primes.next().unwrap(); while p > n { fib.next(); n += 1; } } n += 1; if let Some(f) = fib.next() { if f.is_probably_prime(30) != IsPrime::No { return Some((n - 1, f)); } } })
}
fn to_string(num: &Integer) -> String {
let str = num.to_string(); let len = str.len(); if len > 40 { let mut result = String::from(&str[..20]); result.push_str("..."); result.push_str(&str[len - 20..]); result.push_str(" ("); result.push_str(&len.to_string()); result.push_str(" digits)"); return result; } str
}
fn main() {
use std::time::Instant; let now = Instant::now(); for (i, (n, f)) in prime_fibonacci().take(26).enumerate() { println!("{}: F({}) = {}", i + 1, n, to_string(&f)); } let time = now.elapsed(); println!("elapsed time: {} milliseconds", time.as_millis());
}</lang>
- Output:
1: F(3) = 2 2: F(4) = 3 3: F(5) = 5 4: F(7) = 13 5: F(11) = 89 6: F(13) = 233 7: F(17) = 1597 8: F(23) = 28657 9: F(29) = 514229 10: F(43) = 433494437 11: F(47) = 2971215073 12: F(83) = 99194853094755497 13: F(131) = 1066340417491710595814572169 14: F(137) = 19134702400093278081449423917 15: F(359) = 47542043773469822074...62268716376935476241 (75 digits) 16: F(431) = 52989271100609562179...55134424689676262369 (90 digits) 17: F(433) = 13872771278047838271...25954602593712568353 (91 digits) 18: F(449) = 30617199924845450305...49015933442805665949 (94 digits) 19: F(509) = 10597999265301490732...54396195769876129909 (107 digits) 20: F(569) = 36684474316080978061...15228143777781065869 (119 digits) 21: F(571) = 96041200618922553823...31637646183008074629 (119 digits) 22: F(2971) = 35710356064190986072...48642001438470316229 (621 digits) 23: F(4723) = 50019563612695729290...02854387700053591957 (987 digits) 24: F(5387) = 29304412869392580554...82040327194725855833 (1126 digits) 25: F(9311) = 34232086066590238613...37580645424669476289 (1946 digits) 26: F(9677) = 10565977873308861656...95169792504550670357 (2023 digits) elapsed time: 22642 milliseconds
Sidef
<lang ruby>say 12.by { .fib.is_prime }.map { .fib }</lang>
- Output:
[2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497]
Wren
<lang ecmascript>import "./math" for Int
var limit = 11 // as far as we can go without using BigInt System.print("The first %(limit) prime Fibonacci numbers are:") var count = 0 var f1 = 1 var f2 = 1 while (count < limit) {
var f3 = f1 + f2 if (Int.isPrime(f3)) { System.write("%(f3) ") count = count + 1 } f1 = f2 f2 = f3
} System.print()</lang>
- Output:
The first 11 prime Fibonacci numbers are: 2 3 5 13 89 233 1597 28657 514229 433494437 2971215073
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is prime int N, I; [if N <= 2 then return N = 2; if (N&1) = 0 then return false; for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false; I:= I+1; ];
return true; ];
int F, N, N0, C; [C:= 0; N:= 1; N0:= 1; loop [F:= N + N0;
if IsPrime(F) then [IntOut(0, F); ChOut(0, ^ ); C:= C+1; if C >= 9 then quit; ]; N0:= N; N:= F; ];
]</lang>
- Output:
2 3 5 13 89 233 1597 28657 514229