Eyebrow-raising pattern of number of primes between terms of the Fibonacci number sequence?

So, $$1,1,2,3,5,8,13,21...$$ Any connection to primes?...it appears not. However, in between the Fibonacci numbers are how much primes? Let's see:

• $$1$$ and $$1$$: $$0$$
• $$1$$ and $$2$$: $$0$$
• $$2$$ and $$3$$: $$0$$
• $$2$$ and $$3$$: $$0$$
• $$5$$ and $$8$$: $$1$$
• $$8$$ and $$13$$: $$1$$
• $$13$$ and $$21$$: $$2$$
• $$21$$ and $$34$$: $$3$$
• $$34$$ and $$55$$: $$5$$
• $$55$$ and $$89$$: $$8$$
• $$89$$ and $$144$$: $$13$$

Huh. What could this imply? Let me just close with the same annoying (but wonderful) pattern. $$1,2,3,5,8,13,21...$$

• @HyperLuminal as the rest of people said, it seems to be the "strong law of small numbers", but I like very much when people tries to think different and find new patterns, and I enjoyed this one very much. May 29, 2015 at 0:22
• love this question/thread. if you count the integers that are parts of a pythagorean triple between the fibonaccis, it appears there might be a "fibbonaci-esque" sequence, but frequently off by one. [3 to 5: 4, count = 1] [5 to 8; 7, count = 1] [8 to 13; 9 11 12, count = 3] [13 to 21; 15 16 17 19 20, count = 5] subsequent counts= 9, 15, 25, 40, 66, 107, 174, 282, 457 May 30, 2015 at 23:26
• From an old number theory book: the Fibonacci numbers, divisible by a given prime, are evenly spread in the sequence, for example every third Fibonacci number is even: 2,8,34,144...
– DVD
Jun 4, 2015 at 5:21

Eyebrow raising indeed, though the pattern does not continue as you suggest. I get $$0, 1, 1, 2, 3, 5, 7, 10, 16, 23, 37, 55, 84, 125, 198$$

Remember that the the number of primes has a well known growth rate (https://en.wikipedia.org/wiki/Prime_number_theorem). Since the Fibonacci numbers are relatively spread out, using $n/\log n$ to approximate the number of primes less than $n$ will cause the number of primes between them to behave like the growth rate of the primes.

• This has been considered before. Searching with your data in OEIS gives A052011. May 29, 2015 at 10:19

This is a fun observation... but I think you have a mistake. I wrote a quick python script to generate the fibonacci numbers and primes and make the counts and this is what I get:

Between 5 and 8 there is 1 prime: 7

Between 8 and 13 there is 1 prime: 11

Between 13 and 21 there are 2 primes: 17, 19

Between 21 and 34 there are 3 primes: 23, 29, 31

Between 34 and 55 there are 5 primes: 37, 41, 43, 47, 53

Between 55 and 89 there are 7 primes: 59, 61, 67, 71, 73, 79, 83

Between 89 and 144 there are 10 primes: 97, 101, 103, 107, 109, 113, 127, 131, 137, 139

Between 144 and 233 there are 16 primes: 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229

Between 233 and 377 there are 23 primes: 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373

Between 377 and 610 there are 37 primes: 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607

You can make sense of this pattern (which as yoann points out does not go on very far) as saying that the density of primes is a constant $\phi^{-3}\approx0.236$, since the gap length is $F_{n+1}-F_n=F_{n-1}$ and the conjectured prime count in this gap is $F_{n-4}\approx F_{n-1}\phi^{-3}$.

Unfortunately, this goes against the prime number theorem or various weak versions of it that say that the density of primes goes to $0$ for large $n$, so even without working it out it is clear that the pattern must be short-lived.

(Note: Because the Fibonacci numbers diverge too quickly, the conjectured pattern is not itself sufficient to show that the density of primes is $\phi^{-3}$. But it is enough to prove that the upper density is at least this, which is enough to violate the density zero result. And this is easy to show - considering numbers not divisible by $2,3,5,7$ already gives density $8/35<\phi^{-3}$.)

The pattern does not seem to go on: there are only 17 primes between 144 and 233.

More generally, using the Prime number theorem $\pi(x) \sim_{x \to \infty} \frac x {\ln x}$ (where $\pi(x)$ is and the number of primes lower or equal to $x$), and the formula for the n-th Fibonacci number $F_n \sim_{n \to \infty} \frac{\phi^n}{\sqrt 5}$, we can show that: $$\pi(F_n) \sim_{n \to \infty} \frac{\phi^n}{n \sqrt 5 \ln \phi}$$ The number of primes between two consecutive Fibonacci numbers is therefore: $$\pi(F_{n+1}) - \pi(F_n) \sim_{n \to \infty} \frac{\phi^n (\phi - 1)}{n \sqrt 5 \ln \phi} \sim_{n \to \infty} \frac{\phi - 1}{n\ln \phi} F_n$$.

Which contradicts what you would like to have by a factor of $\frac{\phi - 1}{n\ln \phi}$.

• Why does your figure of 16 primes in [144,233] disagree with @TravisJ’s result of 17? May 29, 2015 at 9:39
• @PJTraill Because 233 is prime. He considered (144,233) while I considered [144,233]. May 29, 2015 at 9:50