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 nth Fibonacci prime number.

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.

Good luck!

Answer 1

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 2

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 3

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 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

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 6

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 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

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 9

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 10

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 11

Javascript:

Number.prototype.fiboN = function()
{
var r = (Math.pow((1 + Math.sqrt(5)) / 2,this) - (Math.pow(1 - (1 + Math.sqrt(5)) / 2,this))) / Math.sqrt(5);
return r.toFixed(0);
}

alert((10).fiboN()); // = 55 assuming the serie starts with 1,1,2,3,5,8,13,...
alert((46).fiboN()); // = 1836311903