Grieve (grieve) wrote,

Prime fibonacci numbers

I was trying to find the first 26 prime fibonacci numbers on Saturday. I didn't think too much about it. I wrote a simple program that used the Sieve of Eratosthenes to find primes. The algorithm was simple, generate fibonacci numbers, and check them for primeness. I found some good programing resources at The Prime Pages

I found 11 prime fibonacci numbers in about 11 seconds. It seemed to stick on the 12th one. I went to bed, thinking that I would have all 26 in the morning. When I woke up, it still hadn't found the 12th one. I was amazed at first, but then I started looking for a pre made list of prime fibonacci numbers on the internet. I found them at page 88. Notice that only 26 of them have been found (at least since 2000).

Also notice the number of digits the last one has 2023. In order to do math on integers of those size you have to use a big number library. I started using NTL. It is an easy package to set up and use.

I want to write a program that will use some of the faster, albeit more complicated, primality tests. Then I will start searching for the next prime fibonacci number. I also need to write the program, so that it can be interrupted, and will continue where it left off. If I find the next fibonacci prime I may win some recognition with my geek friends!

One interesting tidbit I found while researching all of this is that, If F is the fibonacci function, then F(n) is prime only if n is prime! However, if n is prime F(n) is not always prime.

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.