Fibonacci primes and Fibonacci-like sequences

[joshuazelinsky]

Most people have at this point probably heard of the Fibonacci sequence. (Fibonacci actually never went by that name but that's a whole other story.) This sequences goes 1,1,2,3,5,8,13,21,34,55,89...

Each term is made from the sum of the previous two terms. For example, 3+5=8, and then 5+8=13. But since almost everyone has heard of this sequence, it can be a bit boring. So let us spice it up slightly. We could use the same rule for making new terms, but start with any two natural numbers. For example, we could do the sequence 1, 3, 4, 7, 11, 18, 29, 47... Here we started with 1 and 3. Or we could choose some other starting value, say 2 and 2 to get 2, 2, 4, 6, 10, 16, 26... Note that this last sequence isn't very interesting; each term is just twice the corresponding term in the Fibonacci sequence; we could write it as 2(1), 2(1), 2(2), 2(3), 2(5), 2(8), 2(13) and so on. We'll call any sequence which starts with two natural numbers and then makes each new term using the Fibonacci rule Fibonacci-like.

One famous open problem about the Fibonacci sequence is if there are infinitely many Fibonacci numbers which are prime. That is, are there infinitely many numbers like 2, 3, 5, and 13. (7 is prime but not Fibonacci. 8 is Fibonacci but not prime.) We strongly believe the answer is yes. Right now, the largest known Fibonacci prime is F_104911. That is, the 104911th Fibonacci number is prime.

One might note that for small n it seems like F_n is prime if and only if n is prime. This turns out not to be the case. It turns out that if the nth Fibonacci number is prime then one needs that n is prime. But the other direction does not hold. For example, the 19th Fibonacci number, F_19, is 4181 which is 37 times 113.

Since we already had a game where we make Fibonacci-like sequences, and trying to figure out where there are infinitely many Fibonacci primes seems hard, maybe we can look at these Fibonacci-like sequences and see if they help us out. This is something mathematicians do frequently; sometimes when we can't solve something, we look in a more general context and see if it gives us insight. Or at minimum, we at least have a new object which we also don't understand, which is fun too.

So, what happens if we ask if every Fibonacci-like sequence contains infinitely many prime values? Well, here the answer is obviously false. Consider the example we gave above where we had earlier 2, 2, 4, 6, 10, 16... Every term is even, so obviously it doesn't contain any primes after 2. And we can do similar tricks: For example, look at the Fibonacci-like sequence 3, 9, 12, 21, 33, 54, 87... This sequence has every element divisible by 3? Why? Because both the first two terms were divisible by 3, and the sum of two multiples of 3 has to also be a multiple of 3. So at each stage, we get a new multiple of 3.

Given this we can construct a lot of Fibonacci-like sequences which not only don't have infinitely many prime values, they don't have any prime values. For example, we could start with 10, 25 as our starting values, and we'd get a sequence where every term is divisible by 5.

Ok. So our original question had an answer of no. But for boring reasons. Let's call a Fibonacci-like sequence interesting if the first two terms don't have any common factor greater than 1. So the Fibonacci numbers themselves match this, as does our sequence 1, 3, 4, 7, 11... Let's look at a few others: Let's start with 9 and 25. So we get 9,25, 34,59 . Hmm, we eventually got a prime at least. Let's do another, how about 8 and 17. We get 8, 17, 25, 42, 67. Again we got a prime.

Now here's the interesting question: Does every interesting Fibonacci-like sequence eventually have at least one prime value? Perhaps surprisingly, the answer to this is also no. Ron Graham (Who recently passed awy) back in 1964, found that the answer is no. But the starting values Graham found were very big. Since then there's been some effort to find the smallest pair of starting values which don't give rise to any primes. But the smallest known pair today is still very big. It is known that if one starts with 106276436867 and 35256392432 then the resulting Fibonacci-like sequence has no prime values. The basic idea of finding numbers like this is to find a finite set of primes such that any member of one's sequence is divisible by at least one of the primes. But constructing these is hard.

But the existence of Graham-like sequences shows that if there are infinitely many Fibonacci primes, then the proof has to use something deep, beyond just the very basics of the sequence itself. There is however a generalization of the claim that there are infinitely many Fibonacci primes which seems plausible, and I have not seen stated explicitly in the literature. It seems plausible that if a given interesting Fibonacci-like sequence contains at least one prime, then it must contain infinitely many. This is, if true, probably a very difficult thing to prove, since it would be stronger than the apparently tough open problem about Fibonacci primes themselves. If the above is false, it may be that the same techniques as used in Graham's result can find a counterexample. However, it seems likely that there is some number k such that if an interesting Fibonacci-like sequence contains at least k primes then it contains infinitely many.