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 [email protected]

Regards,

Thinh Nghiem

Solution 1:

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.

Solution 2:

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.

[*] https://stackoverflow.com/questions/5563000/implicit-type-conversion-rules-in-c-operators

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