Find the nth Fibonnaci Prime, in the shortest code

Question

The challenge is rather simple:

1. Take a positive whole number \$n\$ as input.
2. Output the \$n\$th Fibonacci prime number, i.e. the \$n\$th Fibonacci number that is also prime.

Input can be as an parameter to a function (and the output will be the return value), or can be taken from the command line (and outputted there).

Note: Using built in prime checking functions or Fibonacci series generators is not allowed.

The first 10 Fibonacci primes are

[2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437]

Shortest code wins. Good luck!

Answer 1

C, 66

f(n,a,b){int i=2;while(a%i&&i++<a);return(n-=i==a)?f(n,b,a+b):a;}

Answer 2

C, 85, 81, 76

f(n){int i=1,j=0,k;for(;n;n-=k==i)for(j=i-j,i+=j,k=2;i%k&&k++<i;);return i;}

• borrowed code style of simplified prime number check from @Gautam

• self contained C function (no globals)

Testing:

main(int n,char**v){printf("%d\n",f(atoi(v[1])));}

./a.out 10
433494437

./a.out 4
13

Answer 3

Ruby, 55

f=->n,a=1,b=2{n<1?a:f[n-(2..b).find{|f|b%f<1}/b,b,a+b]}

Calls itself recursively, keeping track of the last two numbers in the Fibonacci sequence in a and b, and how many primes it's seen so far with n. n gets decremented when the smallest factor greater than 1 of b, divided by b and rounded down to the nearest integer, is 1 rather than 0, which happens only for prime b. When it's seen all the primes it's supposed to, it prints a, which is the most recent b tested for primality.

Answer 4

Mathematica, 59 or 63 bytes

(a=b=1;Do[While[{a,b}={b,a+b};Length@Divisors@b>2],{#}];b)&
(a=b=1;Do[While[{a,b}={b,a+b};b~Mod~Range@b~Count~0>2],{#}];b)&

These are unnamed functions which take n as their input and return the correct Fibonacci prime. The shorter version uses Divisors. I'm not entirely sure whether this is allowed, but the other Mathematica answer even uses FactorInteger.

The second one doesn't use any factorisation related functions at all, but instead counts the number of integers smaller than n which produce 0 in a modulo operation. Even this version beats all valid submissions, but I'm sure just posting this answer will cause some people to provide competitive answers in GolfScript, APL or J. ;)

Answer 5

Mathematica 147 143 141 chars

f@0 = 0; f@1 = 1; f@n_ := f[n - 1] + f[n - 2]
q@1 = False; q@n_ := FactorInteger@n~MatchQ~{{_, 1}}
p = {}; k = 1; While[Length@p < n, If[q@f@k, p~AppendTo~f[k]]; k++];p[[-1]]

f is the recursive definition of Fibonacci number.

q detects primes.

k is a Fibonacci prime iff q@f@k is True.

For n=10, output is 433494437.

Answer 6

Ruby, 94 68 67

n=->j{a=b=1
while j>0
a,b=b,a+b
(2...b).all?{|m|b%m>0}&&j-=1
end
b}

Clojure, 112

Ungolfed:

(defn nk [n]
  (nth 
    (filter
      (fn[x] (every? #(> (rem x %) 0) (range 2 x)))    ; checks if number is prime
      ((fn z[a b] (lazy-seq (cons a (z b (+ a b))))) 1 2)) ; Fib seq starting from [1, 2]
    n)) ; get nth number

Golf: (defn q[n](nth(filter(fn[x](every? #(>(rem x %)0)(range 2 x)))((fn z[a b](lazy-seq(cons a(z b(+ a b)))))2 3))n))

Answer 7

Haskell 108

p=2 : s [3,5..]  where
    s (p:xs) = p : s [x|x<-xs,rem x p /= 0]
f=0:1:(zipWith (+) f$tail f)
fp=intersect p f

To get nth number call it fp !! n.

EDIT: Sic. Wrong answer, I fix it.

Answer 8

Husk, 15 bytes

!fȯ=2LḊ¡oΣ↑_2ḋ3

Try it online!

Answer 9

Groovy: 105 (134 with whitespaces)

b is the fibonacci function.

the closure inside the if is the prime check function. Update: a small fix on it

r is the prime fibonacci number.

r={ n->
  c=k=0
  while(1) {
    b={a->a<2?a:b(a-1)+b(a-2)}
    f=b k++
    if({z->z<3?:(2..<z).every{z%it}}(f)&&c++==n)return f
  }
}

Test cases:

assert r(0) == 0
assert r(1) == 1
assert r(2) == 1
assert r(3) == 2
assert r(4) == 3
assert r(5) == 5
assert r(6) == 13
assert r(7) == 89
assert r(8) == 233
assert r(9) == 1597

A readable version:

def fib(n) { 
  n < 2 ? n : fib(n-1) + fib(n-2)
}
def prime(n) {
  n < 2 ?: (2..<n).every { n % it }
}
def primeFib(n) { 
  primes = inc = 0
  while( 1 ) {
    f = fib inc++
    if (prime( f ) && primes++ == n) return f
  }
}

Answer 10

C, 105 (with spaces)

fibonacci implementation using dynamic programming:

long f(int n){int i;long b2=0,b1=1,n;if(n)return 0;for(i=2;i<n;i++){n=b1+b2;b2=b1;b1=n;}return b1+b2;}

Readable code:

long f(int n)
{
  int i;
  long back2 = 0, back1 = 1;
  long next;
  
  if ( n == 0 ) return 0;

  for ( i=2; i<n; i++ )
  {
    next  = back1 + back2;
    back2 = back1;
    back1 = next;
  }
  
  return back1 + back2;
}

Answer 11

Pyth - 29 bytes

Loops Fibonacci until array is length n but only adds to array if prime.

J2K1W<lYQAJK,+KJJI!tPK~Y]K;eY

Kind of slow, but reached n=10 in ~15 seconds. Can probably be golfed more.

J2              J=2
K1              K=1
W        <lYQ   While length of array<input
 AJK,+KJJ       J,K=K+J,J
 I!tPK          If K prime(not builtin prime function, uses prime factorization)
  ~Y]K          append K to Y
;               End loop so next is printed
eY              last element of Y

Disclaimer: Pyth is newer than this challenge, so not competing.

Answer 12

Jelly, 15 bytes

0+⁸¡1
ÇÆḍ=1µ#ṪÇ

Try it online!

The version that uses builtins is 8 bytes. This is a direct translation of that answer, but with the builtins replaced. This takes input

How it works

0+⁸¡1 - Helper link. Takes k on the left
0     - Set 0 as the left argument
    1 - Set 1 as the right argument
  ⁸¡  - Repeat k times, updating the left and right arguments each time:
 +    -   Add
        This yields the kth Fibonacci number

ÇÆḍ=1µ#ṪÇ - Main link. Takes no input
     µ#Ṫ  - Read an integer n from STDIN and find the nth integer, k, in
            i = 0, 1, 2, ... for which the following is True:
Ç         -   The ith Fibonacci number
 Æḍ       -   Proper divisor count
   =1     -   Equals 1?
        Ç - Yield the kth Fibonacci number

Answer 13

CJam, 31 bytes

1_qi{{_@+_:T,{)T\%!}%:+2>}g}*\;

Try it online!

This is slow.

There is a builtin for primality checking. With that included, it runs much faster, and the size drops to 19 bytes (with the restriction that the supported maximum is 12, because CJam refuses to do a primality check on a BigInt).