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
The first number that was the minus, not the sum was 17. It equals to 19 (prime) - 2 (Fibonacci).
Another person follow my logic to write a programm to calculate up to 10,000. There were 21 failed cases. It needed to be analyzed manually again. But it is really hard work. I will continue, however.
That's a fun question to think about. Reminds me of the typical Project Euler question. ;-)
I saw you got a partial reply via a probabilistic argument on stackexchange. This is nice but it does not guarantee that there are no "outliers" for which no solution exists. As often though it is very easy to verify a solution but comparably much harder to prove that no solution exists.
I tried with a few lines of Matlab just to see what happens and the observation I made is that for some numbers, there is a decomposition of the type P - F, but P and F can be very large.
For example, here are a few "outliers" of smallest decompositions I found that are notoriously large:
- 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 >264. Overall, there are 19 numbers below 10000 for which this is true (and an additional 289 numbers below 100000).
Of course one could go to variable precision arithmetic at this point, but numerics will bring you only so far, if the factors grow exponentially then at some point you won't be able to find them during your lifetime.
*edit* fixed one typo and improved results from int64 to uint64.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Algebra