# 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, 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!

• possible duplicate of Fibonacci function or sequence Aug 15, 2012 at 18:57
• Is there a limit to the size? Aug 26, 2012 at 21:16
• @MrZander Size of what? Aug 27, 2012 at 5:02
• Size of input/output. Do i need to account for prime_fib(1000000000000000000)? Where is the limit? Aug 27, 2012 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. Aug 29, 2012 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. Aug 16, 2012 at 8:28
• Wouldn't a for loop be shorter? (I don't know C well) Aug 16, 2012 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. Aug 16, 2012 at 9:45
• @schnaader of course they worked, but code that sets a & b should be counted because it's codegolf Aug 16, 2012 at 9:54
• Lacks initialisation code for a & b... So can you improve upon just adding g(n){f(n,1,2);}? Aug 18, 2012 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)));}

./a.out 10
433494437

./a.out 4
13


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

# 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. ;)

# 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: Aug 15, 2012 at 20:24
• @acolyte It's fun to look at a trace of a function that calls itself. Aug 15, 2012 at 21:15
• Person: That was one of the courses that confirmed i needed to get the frak out of CompSci. Aug 16, 2012 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 nth number call it fp !! n.

EDIT: Sic. Wrong answer, I fix it.

# Husk, 15 bytes

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


Try it online!

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


# 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;}


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

• How can this have 1 vote? Does not answer the question (no primality check) and the short version does not even compile Jan 31, 2015 at 17:43

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

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


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