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

Question

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...$$

Answer 1

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.

Answer 2

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}$.

Answer 3

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

Answer 4

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}$.)