The Relationships Between Prime Number And Fibonacci Number

[CraigD]

For example 1651 has been expressed successfully as

18446744073709550683 2584 1651.

As Turtle noted, this isn’t solution for P-F=1651, because 18446744073709550683 is not prime. Also, while 2584 is the 19th Fibonacci number, 18446744073709550683-2584 is not 1651.

 

That means the prime number found is over 18 billions billions (Terrible !!!)

There’s nothing terrible about 20 digit decimal numbers, other than that they’re bigger than most programming languages’ built-in integer number types allow. Using the little program I gave in post #22, I’ve checked primes up to 533 digits, and will continue checking even higher.

 

Unless you want to switch to the MUMPS language and use my code, you’ll need to write yours using some sort of arbitrary-precision arithmetic. I gave a link to some existing arbitrary-precision software in this post, and found this somewhat nicer list, also at Wikipedia. You only need to do the basic arithmetic operations on integers, the simplest kind.

 

You could, as I did, write your own arbitrary-precision arithmetic code. It takes some time and effort, but is an educational experience.

[CraigD]

So, in searching for the difference 1651 we can narrow our choices. I'll outline just the cases for Primes ending in 1 and leave the cases of Primes ending in 3, 7, or 9 aside for the time being.

 

Now to get 1651 as a difference between a Prime ending in 1 and a Fibonacci, the Fibonacci must end in 0. Ending digits of Fibonaccis have a cycle of 60, and ending digits of 0 have a sub-cycle of 15. To get P¹-F⁰=1651 you need only check Fibonaccis of form F_(15n) for n={1,2,3,...}

 

Here's the cycle 60 list…

That’s interesting, and leads to knowing how many Fibonacci numbers end in each of the 10 decimal digits by checking the first 60 of them to make this gnarly table:

0   0 15 30 45
1   1  2  8 19 22 28 41 59
2   3 36 54 57
3   4  7 13 26 44 46 47 53
4   9 12 18 51
5   5 10 20 25 35 40 50 55
6  21 39 42 48
7  14 16 17 23 34 37 43 56
8   6 24 27 33
9  11 29 31 32 38 49 52 58

Since I run my program with it displaying the Fibonacci numbers F it checks to see if F+1651 is prime, I’d noticed it progressed in “burst” where the sometimes time-consuming primality tests quickly failed even values F+1651, but I assumed this was happening for about 1/2 of the tries. It’s actually happening for exactly 2/3 of the tries. Making the XRMPT primality test a little smarter by having it immediately fail any number ending in 5 improves this to 11/15

 

Unfortunately, 4/15 of “looks to me like it’ll be forever” is still “looks to me like it’ll be forever”. Computers get slower when the numbers they’re arithmeticing get bigger, and while I’ll let my little laptop PC warm my lap with the 1 of its 4 CPU cores dedicated to running my less-efficient-than-one-written-in-C program, I’m I don’t expect to find Fibonacci number F where F+1651 is prime in the few thousand Fs. I think the lesson from our poor computers here is that we need to stop using brute force (even incrementally more clever brute force) and try to use some number theory.

[Turtle]

That’s interesting, and leads to knowing how many Fibonacci numbers end in each of the 10 decimal digits by checking the first 60 of them to make this gnarly table:

 

 

 

0   0 15 30 45
1   1  2  8 19 22 28 41 59
2   3 36 54 57
3   4  7 13 26 44 46 47 53
4   9 12 18 51
5   5 10 20 25 35 40 50 55
6  21 39 42 48
7  14 16 17 23 34 37 43 56
8   6 24 27 33
9  11 29 31 32 38 49 52 58

Also interesting, if you visited the Fibonacci page, is that

•Suppose we look at the final two digits in the Fibonacci numbers. Do they have a pattern? Yes, there is a pattern here too. After Fib(300) the last two digits repeat the same sequence again and again. The cycle length is 300 this time.

So what about the last three digits?

and the last four digits?

and so on??

 

• For the last three digits, the cycle length is 1,500

• for the last four digits,the cycle length is 15,000 and

• for the last five digits the cycle length is 150,000

• and so on...

Since I run my program with it displaying the Fibonacci numbers F it checks to see if F+1651 is prime, I’d noticed it progressed in “burst” where the sometimes time-consuming primality tests quickly failed even values F+1651, but I assumed this was happening for about 1/2 of the tries. It’s actually happening for exactly 2/3 of the tries. Making the XRMPT primality test a little smarter by having it immediately fail any number ending in 5 improves this to 11/15

 

Unfortunately, 4/15 of “looks to me like it’ll be forever” is still “looks to me like it’ll be forever”. Computers get slower when the numbers they’re arithmeticing get bigger, and while I’ll let my little laptop PC warm my lap with the 1 of its 4 CPU cores dedicated to running my less-efficient-than-one-written-in-C program, I’m I don’t expect to find Fibonacci number F where F+1651 is prime in the few thousand Fs. I think the lesson from our poor computers here is that we need to stop using brute force (even incrementally more clever brute force) and try to use some number theory.

Agreed on 'looks like forever'. Time wise, using my limiting factors is more of an aid to look specifically for 1651, than doing a full search as you fellas are.

 

It may be, though I don't see it yet, that there is some clever way to use the Fibonacci cycles -or other Fibonacci pattern- in comparison to some or other Prime pattern such as prime gaps to disprove theodorenghiem's conjecture.

[theodorenghiem]

Dear all,

 

A number of records in my data output failed since their values were 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.

 

Please access the latest data file and enjoy.

 

Thank you

[CraigD]

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)

Adding a 3rd case to the conjecture, so it is now

Every positive integer can N be expressed as F+P, or F-P or P-F, where P is prime and F a Fibinacci number.

does give a solution to N=1651, but appears to fail again at N=6383.

 

Here’re the additions and changes to the code I gave in post #22:

f  r R q:'$l(R)  s I=$p($p(R,";",$l(R,";")),":") i $l(I) s @I=R ;XRX: read xecute code
n (XCKFPC4,XCKFPC3,XMHI,XRMPT,XMMEXP,R) x XCKFPC3(0) f TC=1:1 s R=","_F1_","_F2 q:TC>NT&NT  s R=N x XCKFPC3(3),XCKFPC3(2) q:R  x XCKFPC3(1) q:R  x XCKFPC4(4) q:R  ;XCKFPC4: check conjecture R=P+F or P-F F-P
s R(1)=FC,R(2)=N x XMHI(">") i R x XMHI("-") s PC=R(3) k R s R=PC x XRMPT s:R R=N_",-"_PC_","_FC ;XCKFPC4(4): N=FC-PC

f N=1:1 s R=N x XRMPT i 'R s R=N_",,,1000" x XCKFPC4 w R,! q:'R

It finds solutions for N= 1 through 6382, but none for N=6383. I’ve checked for Fibonacci numbers through the 375 decimal digit 2100th one.

[theodorenghiem]

Hi CraigD,

 

Yes I also fail with 6383. By the way, I update my latest result. In 10,000,000 there are around 90,000 cases fail. That means 0.9%.

 

Attached is the link of data where you can reference

 

https://drive.google.com/drive/u/0/folders/0BzAetX6K_uyALUc2ZnkzV2xaTkE