The relationships between Prime number and Fibonacci number Dears,
Recently when learning programming language, I accidentally found out an interesting relationship between prime number and Fibonacci number.
That is, a positive integer number can be analyzed as either 
-   the sum of a prime number and a Fibonacci number 
For example 
16 = 11 (prime) + 5 (Fibonnaci)
61 = 59 (prime) + 2 (Fibonacci)
-   or a prime number minus a Fibonacci number
For example
59 = 61 (prime) – 2 (Fibonacci)
83 = 227 (prime) – 144 (Fibonacci)
I have tried with the first 1,000 positive integer number from 1 to 1,000 MANUALLY and ensured that all of them matched with one of the two above rules.
I shared my analyzing here in the excel file with 1,000 positive integer number from 1 to 1,000 with the link
https://drive.google.com/file/d/0BzAetX6K_uyAUXZHQTd5V3ZIa2c/view?usp=sharing
The majority of them belong to the first case are formatted with normal writing. I set the minority cases (the second one where result equals to prime minus Fibonacci) with red and bold format.
So prime number and Fibonacci number are in actual not completely independent with each other.
It is perfect if anyone can prove this rule in general case, or explain its reason. I do not think that this is only an accidental effect.
You can discuss here or email me at theodorenghiem@yahoo.co.nz
Regards,
Thinh Nghiem
 A: Write $F_n$ for the $n$-th Fibonacci number. For $n\geq 2$, $F_n$ is the nearest integer to $((1+\sqrt{5})/2)^n/\sqrt{5}$.
Fix a positive integer $k$. The Prime Number Theorem suggests that the probability that $k+F_n$ is prime is about
$$
\frac{1}{\log\left(k+\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\right)}.
$$
The sum of these probabilities for $n\geq 2$ diverges to $+\infty$ (the $n$-th term is comparable to $n^{-1}$), so we should expect that for each $k$ there are infinitely many values of $n$ for which $k+F_n=p$ is prime. For these $n$, we can write $k=p-F_n$.
Of course this is just a heuristic. There might be some reason $k+F_n$ is more or less likely to be prime than a randomly chosen integer of about the same size. But unless there is a good reason to the contrary, we should expect that every positive integer can be written as $p-F_n$ for some prime $p$ and Fibonacci number $F_n$. That said, statements like this are sometimes very hard to prove.
A: I checked my data. All of the incorrect records belong to Prime numbers which are greater than 2.1 billions. it results from the limit of Java in huge number processing.
I modify the program in C of @Kaynex a little bit to export result to text file. It solve a number of missing records, but not all of them
For example 1651 has been expressed successfully as 
18446744073709550683  2584  1651.That means the prime number found is over 18 billions billions (Terrible !!!)
Finally, there are 9,335,421 numbers from 1 to 10,000,000 are analyzed successfuly. The number of failure is 664,579 records ~ 6.6%.
There may be two cases:


*

*Either the calculation is out of C language capability so it had to break out.

*Or my conjecture fails for these records. That means there is no pair of Prime/Fibonacci to fulfill the rules stated by me.
New data files with the same file names have been uploaded into the same sharing location mentioned above
Thank you @Florian. You are right. The values become so great that they reached out of scope for both C and Java language.
At least by checking them, I found the third rule besides the original ones. It is whole number = Fibonacci - prime.
1651 belongs to this case. In detail: 1651 = 196418 (Fibonacci) - 194767 (Prime)
I have improved my access file in the same shared location in Google drive.
In the fourth column, I noted the format found, For example Prime+Fibonacci, Prime-Fibonacci, Fibonacci-Prime
In my 10,000,000 numbers, there are still 96,634 fails. In my programming, I set it fail when the calculation went out of 2.1 billions (Max for integer in Java). That means 0.97% fail.
Thank you and merry christmas to all of you
