9
\$\begingroup\$

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!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ possible duplicate of Fibonacci function or sequence \$\endgroup\$ – Keith Randall Aug 15 '12 at 18:57
  • 1
    \$\begingroup\$ Is there a limit to the size? \$\endgroup\$ – MrZander Aug 26 '12 at 21:16
  • \$\begingroup\$ @MrZander Size of what? \$\endgroup\$ – Inkbug Aug 27 '12 at 5:02
  • \$\begingroup\$ Size of input/output. Do i need to account for prime_fib(1000000000000000000)? Where is the limit? \$\endgroup\$ – MrZander Aug 27 '12 at 5:58
  • \$\begingroup\$ @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. \$\endgroup\$ – Inkbug Aug 29 '12 at 5:07

13 Answers 13

2
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

C, 66

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

\$\endgroup\$
10
  • 2
    \$\begingroup\$ I think you should define starting values of a and b inside your function. \$\endgroup\$ – defhlt Aug 16 '12 at 8:28
  • \$\begingroup\$ Wouldn't a for loop be shorter? (I don't know C well) \$\endgroup\$ – Inkbug Aug 16 '12 at 8:47
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – schnaader Aug 16 '12 at 9:45
  • 2
    \$\begingroup\$ @schnaader of course they worked, but code that sets a & b should be counted because it's codegolf \$\endgroup\$ – defhlt Aug 16 '12 at 9:54
  • 3
    \$\begingroup\$ Lacks initialisation code for a & b... So can you improve upon just adding g(n){f(n,1,2);}? \$\endgroup\$ – baby-rabbit Aug 18 '12 at 11:00
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

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

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Husk, 15 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
  }
}
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ How can this have 1 vote? Does not answer the question (no primality check) and the short version does not even compile \$\endgroup\$ – edc65 Jan 31 '15 at 17:43
0
\$\begingroup\$

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.
\$\endgroup\$
0
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.