The Relationships Between Prime Number And Fibonacci Number

[theodorenghiem]

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 attached my analyzing here in the excel file with 1,000 positive integer number from 1 to 1,000. 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

Comparison.xlsx

[CraigD]

Welcome to hypography, Theodor! :) Please feel free to start a topic in the introductions forum to tell us something about yourself.

 

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

...

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 have a fascination with things to do with prime numbers, so find this an really interesting conjecture! Thanks for bring it here. :thumbs_up

 

I wrote a quick program to check it using the first 19000 primes (through 212369) and 93 Fibonacci numbers (through 7540113804746346429, the limit of my calculator’s precision). I found prime +/- Fibonacci pairs for integers from 1 to 1044, but couldn’t find one for 1045.

 

Here are all the failures I found for integers up to 10000:

1045, 1351, 1651, 1851, 2185, 2463, 3749, 3901, 4469, 4573, 4773, 5125, 5185, 5215, 5319, 5629, 5731, 5755, 5761, 5949, 6383, 6775, 6851, 6929, 6987, 7259, 7279, 7293, 7375, 7889, 7969, 7981, 8049, 8339, 8347, 8349, 8491, 8553, 8557, 8877, 9081, 9121, 9267, 9359, 9361, 9409, 9527, 9569, 9945

 

Can you find solution for these?

[A-wal]

I have a fascination with things to do with prime numbers, so find this an really interesting conjecture! Thanks for bring it here. :thumbs_up

Me too simply because there's no known progression formula sequence for them when you'd (or at least I would) think they'd be a straight forward one. Whole numbers that can only by divided by whole numbers to produce whole numbers that are 1 or that number, should be a simple formula. I'm also fascinated by the Fibonacci sequence.

 

Recently when learning programming language, I accidentally found out an interesting relationship between prime number and Fibonacci number.

When I was learning programming language I accidentally found this: 1/01.618033988749895 = 0.618033988749895. Learning to program open my mind in a lot of ways that I wasn't expecting.

 

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.

Interesting.

 

I wrote a quick program to check it using the first 19000 primes (through 212369) and 93 Fibonacci numbers (through 7540113804746346429, the limit of my calculator’s precision). I found prime +/- Fibonacci pairs for integers from 1 to 1044, but couldn’t find one for 1045.

 

Here are all the failures I found for integers up to 10000:

1045, 1351, 1651, 1851, 2185, 2463, 3749, 3901, 4469, 4573, 4773, 5125, 5185, 5215, 5319, 5629, 5731, 5755, 5761, 5949, 6383, 6775, 6851, 6929, 6987, 7259, 7279, 7293, 7375, 7889, 7969, 7981, 8049, 8339, 8347, 8349, 8491, 8553, 8557, 8877, 9081, 9121, 9267, 9359, 9361, 9409, 9527, 9569, 9945

I hope you find a solution to this!

[theodorenghiem]

Thank you CraigD. I will check and answer you

[Mariel33]

I've read with interest some of the previous posts. I'm unsure about the true significance, to do with a prime and Fibonacci number both adding and subtracting to result in a positive integer - am I right in thinking it's because of a duplication principle? 

 

[Turtle]

Welcome to hypography, Theodor! :) Please feel free to start a topic in the introductions forum to tell us something about yourself.

 

I have a fascination with things to do with prime numbers, so find this an really interesting conjecture! Thanks for bring it here. :thumbs_up

 

I wrote a quick program to check it using the first 19000 primes (through 212369) and 93 Fibonacci numbers (through 7540113804746346429, the limit of my calculator’s precision). I found prime +/- Fibonacci pairs for integers from 1 to 1044, but couldn’t find one for 1045.

 

Here are all the failures I found for integers up to 10000:

1045, 1351, 1651, 1851, 2185, 2463, 3749, 3901, 4469, 4573, 4773, 5125, 5185, 5215, 5319, 5629, 5731, 5755, 5761, 5949, 6383, 6775, 6851, 6929, 6987, 7259, 7279, 7293, 7375, 7889, 7969, 7981, 8049, 8339, 8347, 8349, 8491, 8553, 8557, 8877, 9081, 9121, 9267, 9359, 9361, 9409, 9527, 9569, 9945

 

Can you find solution for these?

 

 

Interesting.

 

I hope you find a solution to this!

 

Craig was being facetious, which is to say there is no solution and the OP is mistaken in there being a general rule for all primes under his conjecture. There are countless such coincidences which start in a promising manner and sooner-than-later fail under scrutiny. Cest la vie.

[A-wal]

Craig was being facetious, which is to say there is no solution and the OP is mistaken in there being a general rule for all primes under his conjecture. There are countless such coincidences which start in a promising manner and sooner-than-later fail under scrutiny. Cest la vie.

There IS a general rule for the sequence of all prime numbers! It might not have anything to do with the Fibonacci sequence but there has to be one because what makes a number prime is a well defined rule, so it has to follow a well defined progression formula. It's fascinating that it's apparently so ridiculously complicated for such a simple rule that nobody's figured it out.

[exchemist]

There IS a general rule for the sequence of all prime numbers! It might not have anything to do with the Fibonacci sequence but there has to be one because what makes a number prime is a well defined rule, so it has to follow a well defined progression formula. It's fascinating that it's apparently so ridiculously complicated for such a simple rule that nobody's figured it out.

Says who? Wiki at least disagrees: "There is no known simple formula that separates prime numbers from composite numbers."

 

(From this link: https://en.wikipedia.org/wiki/Prime_number )

[A-wal]

Says who? Wiki at least disagrees: "There is no known simple formula that separates prime numbers from composite numbers."

 

(From this link: https://en.wikipedia.org/wiki/Prime_number )

Which is precisely why it's so fascinating. There must be a formula because prime numbers follow a purely mathematical and deceptively simple rule but the formula governing their progression must be extremely complex.

[OceanBreeze]

Which is precisely why it's so fascinating. There must be a formula because prime numbers follow a purely mathematical and deceptively simple rule but the formula governing their progression must be extremely complex.

There does seem to be a pattern to them. Just a matter of working it out, right?

 

https://www.youtube.com/watch?v=iFuR97YcSLM

[Turtle]

There IS a general rule for the sequence of all prime numbers! It might not have anything to do with the Fibonacci sequence but there has to be one because what makes a number prime is a well defined rule, so it has to follow a well defined progression formula. It's fascinating that it's apparently so ridiculously complicated for such a simple rule that nobody's figured it out.

There is a simple definition, period. Your double-speak, i.e. complicated simplicity, is nothing more than useless babble. Ooooo, it's bolded uppercase so that makes me right. :doh: Moreover, Gödel made clear that there does not have to be any such 'rule' as you imply.

[A-wal]

Your double-speak, i.e. complicated simplicity, is nothing more than useless babble.

It's not double speak you ninny. It's a very simple rule that makes a prime number and it leads to a complex progression formula.

 

Ooooo, it's bolded uppercase so that makes me right. :doh:

It's called emphasis, although technically I suppose it should have been 'There is a general rule...'

 

Moreover, Gödel made clear that there does not have to be any such 'rule' as you imply.

Of course there's a rule! How can any mathematical progression that isn't random possibly not have a rule? It's just that the amount of examples needed to see the pattern must be huge.

[Turtle]

It's not double speak you ninny. It's a very simple rule that makes a prime number and it leads to a complex progression formula.

Just keep telling yourself that.

 

It's called emphasis, although technically I suppose it should have been 'There is a general rule...'

Unjustified emphasis is called posturing.

 

Of course there's a rule! How can any mathematical progression that isn't random possibly not have a rule? It's just that the amount of examples needed to see the pattern must be huge.

So say you. Fortunately, actual mathematicians have a better grasp of the matter.

 

Mathematicians Discover Prime Conspiracy: A previously unnoticed property of prime numbers seems to violate a longstanding assumption about how they behave.

 

...Yet the pair’s work doesn’t upend the notion that primes behave randomly so much as point to how subtle their particular mix of randomness and order is. “Can we redefine what ‘random’ means in this context so that once again, [this phenomenon] looks like it might be random?” Soundararajan said. “That’s what we think we’ve done.” ...

The very reason that primes generate so much interest is that for all intents and purposes, they are random. While pursuing explorations such as in the OP or the article linked above has great appeal to many, making emphatic proclamations without proof is a mark of the uninformed.

[A-wal]

Look you miserable piece of 'I have a massive amount of sand in my vagina', how the hell is saying that prime numbers follow a very simple rule but lead to a very complex progression rate in any way double speak?

 

I don't give a flying monkeys what people you view as authority figures say about this particular (specifically the progression formula) issue because prime numbers aren't random.

If they're not random then they MUST follow a progression formula.

Edited November 18, 2016 by A-wal

[CraigD]

OK, stop with the name-calling! It’s not mathematically helpful. :thumbs_do

 

Craig was being facetious, which is to say there is no solution and the OP is mistaken in there being a general rule for all primes under his conjecture.

I wasn’t be facetious, nor have I disproven Theodorenghiem’s conjecture.

 

I quickly wrote a program that found that n=1045 can’t be given by n = p ± f where p is a prime not more than 212369 and f a Fibonacci number not more than 7540113804746346429. This isn’t a disproof by example, though, because of the tricky n = p – f part of n = p ± f. Unlike n = p + f, a failure can’t be found by exhaustively trying every possible p and f not greater than n. There might be p and f larger than any tried for which n = p – f.

 

It may be possible to disprove the conjecture, but the quick and easy trick of having a computer exhaustively try every p and f can’t do it. Someone needs to cleverer. :) It might also be possible to prove it, though my intuition is nudging me in the disprove direction.

 

I think it’s important to note that, even if proven true, the conjecture can’t be turned into a prime number generator, because given an integer n and a Fibonacci number f, it doesn’t guarantee p = n -f or n +f is prime.

 

You can disprove that any polynomial using Fibonacci numbers can generate the primes, because the Fibonacci numbers can be generated with a polynomial, so any polynomial using them is simply a polynomial, and it’s proven that no polynomial can generate only primes.

 

 

There IS a general rule for the sequence of all prime numbers! It might not have anything to do with the Fibonacci sequence but there has to be one because what makes a number prime is a well defined rule, so it has to follow a well defined progression formula. It's fascinating that it's apparently so ridiculously complicated for such a simple rule that nobody's figured it out.

What do you mean, precisely, by “well defined progression formula”?

 

We need to be careful with phrases like this, because as I mention above, it has been proven that some kinds of formulae, such as polynomials, absolutely cannot generate even a subset of the prime numbers. It’s also been shown that some kinds of formulas like this system of Diophantine equations, can generate them all. Such formulas, however, are more computational difficult to solve than next prime number generating programs that use the simple approach:

• Start with pc = pm the previous greatest known prime number
• Add 2 to pc
• Check to see if pc is is prime. If it is, the new pm = pc
• If not, repeat from step 2

The computationally hard part is step 3, checking to see if pc is prime. In practice, for large numbers, it’s often better to use a test that isn’t certain to be correct (deterministic), but has a probability of being incorrect much lower than the probability of something else in the computer going wrong. The Rabin–Miller test is a common probabilistic primacy test.

 

It’s good to keep a perspective on questions involving prime numbers. I think there are 2 fundimental kinds:

• what are the factors of an integer N
• what is the Nth prime number

. Both can be answered with brute force, but for numbers we can easily represent, the amount of brute force needed for all known algorithms is greater than the amount of arithmetic computation possible in the lifetime of the universe.

[Turtle]

I wasn’t be facetious, nor have I disproven Theodorenghiem’s conjecture.

Your 'I hope you find a solution to this!' struck me as amusing, whether you intended it or not. Given your comment 'Both can be answered with brute force, but for numbers we can easily represent, the amount of brute force needed for all known algorithms is greater than the amount of arithmetic computation possible in the lifetime of the universe.', which I assumed you knew, and given theodorenghiem's brute force OP, by asking theodorenghiem for a solution you are mapping a rather ridiculous journey. Well, humor is as humor does. :shrug:

 

Unlike n = p + f, a failure can’t be found by exhaustively trying every possible p and f not greater than n. There might be p and f larger than any tried for which n = p – f.

Agreed.

 

Someone needs to cleverer. :) It might also be possible to prove it, though my intuition is nudging me in the disprove direction.

Cleverer indeed. I was thinking there may be some clever lever in the fact that there exist Fibonacci Primes, but that is another inscrutable nut for which we haven't enough time.

[A-wal]

What do you mean, precisely, by “well defined progression formula”?

NextPrime = (PreviousPrime / Phi^2) - Previous Prime + 1 x Previous Prime... For example.

 

I'm interested to see if Theodorenghiem's idea can work.