# 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

• This is a pretty cool rule, I would like to hear more about it too. But, keep in mind that 1 is not considered a prime number. You've got 9 = 1 + 8, which doesn't work. However, 9 = 7 + 2 does. It may be worth testing this for more numbers than 1000. – Kaynex Nov 17 '16 at 1:31
• Well, I've verified this for the first 10,000,000 integers. – Kaynex Nov 17 '16 at 6:05
• Interesting question! – Peter Nov 17 '16 at 22:11
• Have you checked to see which ones can be Fibonacci - prime? Or which numbers can be expressed as a difference or a sum of the two? Very interesting! – Bonnaduck Nov 18 '16 at 6:17
• As the answer below shows, "most" asymptotically exponential sequences would be expected to have this property. There are certain cases where it is obviously not true - such as when the sequence is always even or odd - but otherwise, it would not be a surprising property of the sequence to not have this property. – Thomas Andrews Nov 28 '16 at 1:29

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.

• Actually, $F_n$ is the nearest integer to $$\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n$$ Doesn't affect your result. – Thomas Andrews Nov 27 '16 at 23:13
• But there are infinitely many numbers that cannot be written as $p-2^n$ (these are sometimes called dual-Sierpinski numbers), even though the same heuristic applies to this sequence. The Fibonacci sequence behaves in many ways like an exponential sequence (e.g. periodicity of residues), so it would be interesting to see if the same covering congruence technique can be used on this question. – Erick Wong Dec 16 '16 at 10:44
• @Erick That's a good point, I was not aware of the dual-Sierpinski numbers. Now I think my belief has shifted towards the conjecture being false. – Julian Rosen Dec 16 '16 at 18:27

As a small addition, I would like to object to Kaynex comment that it is easy to verify this statement for integers up to 10^7.

@Kaynex: Thanks for your efforts and thanks for sharing your code! The main problem in your code is that you declare fib2 as unsigned long long whereas the number to be tested is only int. Therefore:

@l25: if (j-fib2>0) will not work. Since fib2 is unsigned long long, C++ will promote j also to unsigned long long [*]. Then j-fib2 will also be unsigned and therefore an overflow occurs whenever fib2>j. Fixed by testing if (j>fib2) intead.

@l25: the result of this is passed to primecheck whose argument is only an int. There goes your long long and your unsigned. In the case mentioned above you'll prime-test a negative. Fixed by changing all ints to unsigned long long.

@l30: same problem with isprime. Fixed by changing all ints to unsigned long long.

If you make these fixes you will see that some numbers have decompositions P-F with notoriously large Fibonacci numbers F. I ran some Matlab-based experiments and here are some notable examples I found:

• 1351 = 14931703 - 14930352 (F36).
• 1851 = 267916147 - 267914296 (F42).
• 3089 = 1134906259 - 1134903170 (F45).
• 4573 = 4807531549 - 4807526976 (F48).
• 2953 = 1548008758873 - 1548008755920 (F60).
• 5755 = 27777890041043 - 27777890035288 (F66).
• 1499 = 160500643816368587 - 160500643816367088 (F84).
• 1861 = 679891637638614119 - 679891637638612258 (F87).
• 8553 = 2880067194370824673 - 2880067194370816120 (F90).
• 45509 = 12200160415121922247 - 12200160415121876738 (F93).

I searched the whole range of uint64 for P and F and the smallest numbers that had no match were 1651, 1759, 2185, .... This does not mean they have none, it just means that if they have one, P and F must be >2^64. Overall, there are 19 numbers below 10000 for which this is true (and an additional 289 numbers below 100000). 5 of the 19 are prime themselves so if we include 0 as a valid Fibonacci number, it reduces to 14 below 1000 (216 below 10000).

I tried finding a decomposition for 1651 beyond uint64 using variable-precision arithmetic but my prime tests on this are just too slow. For me, this is where the numerics end.

edit: There is more! I recently fell in love with SageMath which allowed me to search a bit further since for some reason its prime test is just crazy fast even for very large integers.

Here are 18 of the 19 missing matches below 10000:

• $F_{105} + N$ is prime for $N=5569,5731,8347$.
• $F_{120} + N$ is prime for $N=9409$.
• $F_{129} + N$ is prime for $N=8877$.
• $F_{135} + N$ is prime for $N=1651,1759$.
• $F_{156} + N$ is prime for $N=4597$.
• $F_{183} + N$ is prime for $N=3079$.
• $F_{195} + N$ is prime for $N=4773,8049$.
• $F_{207} + N$ is prime for $N=5629$.
• $F_{210} + N$ is prime for $N=9081$.
• $F_{276} + N$ is prime for $N=2185$.
• $F_{303} + N$ is prime for $N=3697$.
• $F_{396} + N$ is prime for $N=7889$.
• $F_{453} + N$ is prime for $N=7259$.
• $F_{2487} + N$ is prime for $N=7293$.

The last one is already of order $F_{2487} \approx 2^{1726} \approx 10^{519.6}$.

One number is still open which is 6851. I was able to search until $F_{13224} \approx 2^{9179.5} \approx 10^{2763.3}$. At this point, the prime test of Sage failed (due to some overflow in the Pari library it is calling for this job). I'm pretty confident that 6851 will have a match as well. Might just be quite big.

• @Thinh Nghiem: FYI, I improved the search quite a bit more using SageMath. See my edit to this reply. – Florian Dec 31 '16 at 16:10

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:

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

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

• @Kaynex The decomposition for 1651 you found is incorrect: 18446744073709550683 is not a Fibonacci number. The largest Fibonacci number that fits into a uint64 is F93=12,200,160,415,121,876,738. The next one would be F94=19,740,274,219,868,223,167. The one you mention for 1651 is inbetween and very close to 2^64=18,446,744,073,709,551,616. So I'm assuming you suffered an integer overflow. Going beyond uint64 is not trivial to program since there is no native support by current CPUs, you have to emulate it using some variable precision arithmetic (which is usually quite slow). – Florian Dec 19 '16 at 8:24
• To verify your results for very large Fibonacci numbers, consider consulting a table, like this one: maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html – Florian Dec 19 '16 at 8:25