# Prime distribution in the Fibonacci sequence and Pell sequence gaps

first time posting here.

I was recently reading on primes and the Pell numbers, and I asked myself "what about primes between the Pell numbers?" as I hurried to a piece of paper with a pen to search for patterns.

And surprisingly something pattern-like I found.

I first looked at the numbers of primes between two successive Pell numbers, say P_4 and P_5, then I looked at the next two successive Pell numbers, P_5 and P_6, did the same thing and then divided the first number of primes by the second number of primes.

Basically, multiplication factor = (number of primes between two successive Pell numbers) / (number of prime between next two successive Pell numbers).

For the first Pell numbers, small enough to do the math on paper, I found that this multiplication factor seems to stick to around 2.

So I wrote a Java program to test this out, and using the BPSW primality test for large numbers to make things more efficient.

public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter n the number of 2-Bonnacci series to calculate");
int n = scanner.nextInt();
scanner.close();
List<Integer> serie = new ArrayList<Integer>();
for (int i = 2; i <= n; i++) {
serie.add(i, 2 * serie.get(i - 1) + serie.get(i - 2));
Collections.sort(serie);
}
System.out.println("Finished generating serie");
double s = 0;
double sNext;
long startTime;
long endTime;
System.out.println("The last number of the serie is " + serie.get(n - 1));
for (int i = 0; i < n; i++) {
startTime = System.nanoTime();
if (i + 1 == 1) {
System.out.println("Calculating the " + (i + 1) + "st gap.");
} else if (i + 1 == 2) {
System.out.println("Calculating the " + (i + 1) + "nd gap");
} else {
System.out.println("Calculating the " + (i + 1) + "th gap");
}
sNext = s;
s = 0;
if (serie.get(i) + 1 == serie.get(i + 1)) {

} else {
for (int k = serie.get(i) + 1; k < serie.get(i + 1); k++) {

// BPSW Primality Test.
BigInteger kk = BigInteger.valueOf(k);
if (isProbablePrime(kk, 15)) {
s++;
}

}
}
endTime = System.nanoTime();
if (sNext == 0) {
sNext = 1;
} else {
}
System.out.print(i + "  ");
System.out.print("Number of prime in gap is " + s + "  ");
System.out.println("Multiplication factor compared to last gap is " + s / sNext);
System.out
.println("Runtime for this gap is " + (double) ((endTime - startTime) / 1000000000.0) + " seconds");
}

}

private static final BigInteger ZERO = BigInteger.ZERO;
private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = new BigInteger("2");
private static final BigInteger THREE = new BigInteger("3");

public static boolean isProbablePrime(BigInteger n, int k) {
if (n.compareTo(ONE) == 0)
return false;
if (n.compareTo(THREE) < 0)
return true;
int s = 0;
BigInteger d = n.subtract(ONE);
while (d.mod(TWO).equals(ZERO)) {
s++;
d = d.divide(TWO);
}
for (int i = 0; i < k; i++) {
BigInteger a = uniformRandom(TWO, n.subtract(ONE));
BigInteger x = a.modPow(d, n);
if (x.equals(ONE) || x.equals(n.subtract(ONE)))
continue;
int r = 0;
for (; r < s; r++) {
x = x.modPow(TWO, n);
if (x.equals(ONE))
return false;
if (x.equals(n.subtract(ONE)))
break;
}
if (r == s) // None of the steps made x equal n-1.
return false;
}
return true;
}

private static BigInteger uniformRandom(BigInteger bottom, BigInteger top) {
Random rnd = new Random();
BigInteger res;
do {
res = new BigInteger(top.bitLength(), rnd);
} while (res.compareTo(bottom) < 0 || res.compareTo(top) > 0);
return res;
}


After a few tests to make sure that everything is working as intended, I launched it for n=25.

The output:

Enter n the number of 2-Bonnacci series to calculate

25

Finished generating serie

The last number of the serie is 543339720

Calculating the 1st gap.

0 Number of prime in gap is 0.0 Multiplication factor compared to last gap is 0.0

Runtime for this gap is 3.355E-5 seconds

Calculating the 2nd gap

1 Number of prime in gap is 0.0 Multiplication factor compared to last gap is 0.0

Runtime for this gap is 2.0057E-5 seconds

Calculating the 3rd gap

2 Number of prime in gap is 1.0 Multiplication factor compared to last gap is 1.0

Runtime for this gap is 9.61275E-4 seconds

Calculating the 4th gap

3 Number of prime in gap is 2.0 Multiplication factor compared to last gap is 2.0

Runtime for this gap is 0.001261036 seconds

Calculating the 5th gap

4 Number of prime in gap is 4.0 Multiplication factor compared to last gap is 2.0

Runtime for this gap is 0.002815999 seconds

Calculating the 6th gap

5 Number of prime in gap is 9.0 Multiplication factor compared to last gap is 2.25

Runtime for this gap is 0.00467218 seconds

Calculating the 7th gap

6 Number of prime in gap is 20.0 Multiplication factor compared to last gap is 2.2222222222222223

Runtime for this gap is 0.00593504 seconds

Calculating the 8th gap

7 Number of prime in gap is 40.0 Multiplication factor compared to last gap is 2.0

Runtime for this gap is 0.01171801 seconds

Calculating the 9th gap

8 Number of prime in gap is 87.0 Multiplication factor compared to last gap is 2.175

Runtime for this gap is 0.012972119 seconds

Calculating the 10th gap

9 Number of prime in gap is 186.0 Multiplication factor compared to last gap is 2.1379310344827585

Runtime for this gap is 0.014431537 seconds

Calculating the 11th gap

10 Number of prime in gap is 402.0 Multiplication factor compared to last gap is 2.161290322580645

Runtime for this gap is 0.033172403 seconds

Calculating the 12th gap

11 Number of prime in gap is 882.0 Multiplication factor compared to last gap is 2.1940298507462686

Runtime for this gap is 0.075271617 seconds

Calculating the 13th gap

12 Number of prime in gap is 1944.0 Multiplication factor compared to last gap is 2.204081632653061

Runtime for this gap is 0.128184819 seconds

Calculating the 14th gap

13 Number of prime in gap is 4324.0 Multiplication factor compared to last gap is 2.2242798353909463

Runtime for this gap is 0.30185702 seconds

Calculating the 15th gap

14 Number of prime in gap is 9668.0 Multiplication factor compared to last gap is 2.2358926919518964

Runtime for this gap is 0.49462455 seconds

Calculating the 16th gap

15 Number of prime in gap is 21721.0 Multiplication factor compared to last gap is 2.24669011170873

Runtime for this gap is 1.162513597 seconds

Calculating the 17th gap

16 Number of prime in gap is 49080.0 Multiplication factor compared to last gap is 2.259564476773629

Runtime for this gap is 2.731212182 seconds

Calculating the 18th gap

17 Number of prime in gap is 111238.0 Multiplication factor compared to last gap is 2.2664629176854114

Runtime for this gap is 6.605702962 seconds

Calculating the 19th gap

18 Number of prime in gap is 253153.0 Multiplication factor compared to last gap is 2.2757780614538197

Runtime for this gap is 15.693769467 seconds

Calculating the 20th gap

19 Number of prime in gap is 578020.0 Multiplication factor compared to last gap is 2.283283231879535

Runtime for this gap is 37.899228682 seconds

Calculating the 21th gap

20 Number of prime in gap is 1323430.0 Multiplication factor compared to last gap is 2.289592055638213

Runtime for this gap is 92.762226819 seconds

Calculating the 22th gap

21 Number of prime in gap is 3038548.0 Multiplication factor compared to last gap is 2.2959642746499624

Runtime for this gap is 233.569712007 seconds

Calculating the 23th gap

22 Number of prime in gap is 6993171.0 Multiplication factor compared to last gap is 2.3014844590245076

Runtime for this gap is 560.457488889 seconds

Calculating the 24th gap

23 Number of prime in gap is 1.6128245E7 Multiplication factor compared to last gap is 2.3062849456991685

Runtime for this gap is 1360.104659453 seconds

Calculating the 25th gap

24 Number of prime in gap is 3.7273978E7 Multiplication factor compared to last gap is 2.3110994407637038

Runtime for this gap is 3344.46182557 seconds

While 25 samples is indeed few, as you can see, the time needed to calculate the 24th gap is almost an hour long.

While I cannot say anything more than "oh look this serie seems to possess a limit" the fact that the number of primes between each Pell numbers grows at a specific rate is eyebrow-raising. I also find it peculiar that the limit of this serie seems to be the silver ratio, the number defining the Pell sequence, which is even more eyebrow-raising.

However, as I said above, all this is but speculation, and I do not have the tools nor the knowledge to prove these speculations.

That said, I did not stop at the Pell sequence, as the title says. I did this too for the Fibonacci sequence, and the results were even more surprising.

The algorithm stays the same, I just modified the sequence generator to fit the Fibonacci sequence.

This time I could take 40+ samples without problems, but I only took 40 for the sake of time (the 39th gap took 180 seconds to finish).

https://plot.ly/~jonathan.dubruel/1/

Above are the output of the algorithm and a plot I made with the results.

As you can see, this time the serie seems to tend toward a limit, at least more clearly than for the Pell sequence. And again, the limit seems to be the golden ratio.

This is all I did before I realised I need help, or at least someone telling me this has already been done and that I could read on it somewhere. But I haven't found a single article about this anywhere, maybe because I'm not looking for it where I should.

Anyway, I find this extremely surprising, and did not expect such patterns for primes and these sequences, and I ask for the opinion of more experienced mathematicians and experts on this subject.

• That's a very long question... – Lord Shark the Unknown May 12 '18 at 11:00
• Most of it is just clarifying what I used for my deduction though :) – Jonathan Dubruel May 12 '18 at 11:06

Let us consider the number of primes between $F_n$ and $F_{n+1}$. This is $$\pi(F_{n+1})-\pi(F_n).$$ Using the prime number theorem: $\pi(x)\sim x/\ln x$, and the fact that $F_{n+1}\approx\tau F_n$ (where $\tau$ is the golden ratio), this is approximately $$\frac{\tau F_n}{\ln(\tau F_n)}-\frac{F_n}{\ln F_n} =\frac{F_n}{\ln F_n}\left(\frac\tau{1+\ln(\tau)/\ln F_n}-1\right)$$ which is even more roughly $$(\tau-1)\frac{F_n}{\ln F_n}.$$ Then the ratio $$\frac{\pi(F_{n+2})-\pi(F_{n+1})}{\pi(F_{n+1})-\pi(F_n)}$$ is roughly $$\frac{F_{n+1}\ln F_n}{F_n\ln F_{n+1}}\approx\tau.$$