# Find the nth Fibonnaci Prime, in the shortest code

The challenge is rather simple:

1. Take a positive whole number `n` as input.
2. Output the `n`th 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!

-
possible duplicate of Fibonacci function or sequence – Keith Randall Aug 15 '12 at 18:57
Is there a limit to the size? – MrZander Aug 26 '12 at 21:16
@MrZander Size of what? – Inkbug Aug 27 '12 at 5:02
Size of input/output. Do i need to account for prime_fib(1000000000000000000)? Where is the limit? – MrZander Aug 27 '12 at 5:58
@MrZander The algorithm should support arbitrarily large numbers, but the function may raise an out of bound exception if the result is too big for a normal int. – Inkbug Aug 29 '12 at 5:07

# C, 66

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

-
I think you should define starting values of `a` and `b` inside your function. – Artem Ice Aug 16 '12 at 8:28
Wouldn't a for loop be shorter? (I don't know C well) – Inkbug Aug 16 '12 at 8:47
Can be reduced to 65 chars: `f(n,a,b){int i=2;while(a%i&&i++<a);return(n-=i==a)?f(n,b,a+b):a;}` - @ArtemIce: `a`= 1 and `b`= 2 worked for me. – schnaader Aug 16 '12 at 9:45
@schnaader of course they worked, but code that sets a & b should be counted because it's codegolf – Artem Ice Aug 16 '12 at 9:54
Lacks initialisation code for a & b... So can you improve upon just adding `g(n){f(n,1,2);}`? – baby-rabbit Aug 18 '12 at 11:00

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

# 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`.

-
 oh god, induction...:shudders: – acolyte Aug 15 '12 at 20:24 @acolyte It's fun to look at a trace of a function that calls itself. – David Carraher Aug 15 '12 at 21:15 Person: That was one of the courses that confirmed i needed to get the frak out of CompSci. – acolyte Aug 16 '12 at 1:11

# 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))`

-

``````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 `n`th number call it `fp !! n`.

EDIT: Sic. Wrong answer, I fix it.

-

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

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

Here is a solution in APL:

``````{⊃({(+/⍵),⊃⍵}⍣(⍵-1))1}
``````

It is iterative and uses the standard accumulative algorithm.

[Whoops! This is for Fibonnacci Primes...the above is just regular primes.]

-