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 serie = new ArrayList();
serie.add(0, 0);
serie.add(1, 1);
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.
Answer
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.$$
No comments:
Post a Comment