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...$$
Solution 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.
Solution 2:
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
Solution 3:
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}$.)