6
$\begingroup$

I am trying to devise a recursive prime-generating function following an intuition of a possible analogy to Mills and Wright prime-representing functions, in the present case based on logarithms. The proposed prime generating function $f(n)$ will provide not a subset but the complete set of primes being $f(1)=2$, $f(2)=3$, $f(3)=5$... and the prime-generating constant will be called $L$. As in the standard results from Mills and Wright the decimal precision of the constant is important in order to recover the embedded primes and it is not known if $\lim_{n \to \infty} L_n$ is rational or not.

This is how it works and the questions are at the end:

  1. Start with $n=1$, current prime $p_1=2$, previous accumulated value of the constant will be defined as $L_0=0$ (starting value). Calculate the value for the constant for $n=1$. It will be $$L_1=\frac{Ln(2+L_0)}{Ln(1+1)}$$

(Where $Ln$ is the natural logarithm).

  1. Calculate the value for the constant for $n=2$, $p_2=3$, $$L_2=\frac{Ln(3+L_1)}{Ln(2+1)}$$

So if we apply recursively the formula, for $n$:

$$L_n=\frac{Ln(p_n+L_{n-1})}{Ln(n+1)}$$

For instance, the following PARI_GP code calculates $L_{500}$

\p2000;
testlimit=500;current_pr=2;L=0;for(n=1,testlimit,L=log(current_pr+L)/log(n+1);current_pr=nextprime(current_pr+1););print("n is ",testlimit," and L is ",L);

$$L_{500} = 1.3159864456...$$

Reviewing the results of the tests, it seems that $\lim_{n \to \infty} L_n$ oscillates (due to the gaps between primes applied in the formula) but in the long term it is stable and tends to decrease and goes down to a value closer to $1$ and lower than $2$.

For example:

\p3;
testlimit=500000;current_pr=2;L=0;for(n=2,testlimit,L=log(current_pr+L)/log(n);current_pr=nextprime(current_pr+1););print("n is ",testlimit," and L is ",L);

$L_{5000}$ is around $1.23...$ and the above code shows that $L_{500000}$ is around $1.21$. Other similar tests show that it tends to go down to some specific limit near the lower bound of $[1,2]$.

As the proccess of recovering the primes is recursive, the way of using the constant is as follows:

For instance, assuming that we have $L_{500}$, we need to start obtaining the last prime back:

$$f(500)=p_{500}=\lfloor (500+1)^{L_{500}} \rfloor - 1 = 3571$$

Then recover $L_{499}$ and recover $f(499)=p_{499}$

$$L_{499}=((500+1)^{L_{500}})-p_{500}=1.31586811...$$

$$f(499)=p_{499}=\lfloor (499+1)^{L_{499}} \rfloor - 1 = 3559$$

$$...$$

So in general the recursive process to recover $L_{n}$ and $f(n)=p_n$ from $L_{n+1}$ and $f(n+1)=p_{n+1}$ is:

$$L_{n}=((n+2)^{L_{n+1}})-p_{n+1}$$

$$f(n)=p_{n}=\lfloor (n+1)^{L_{n}} \rfloor - 1$$

The following code, having $L_{500}$ calculates backwards the complete set of primes $\{p_{500}..p_{1}\}$

curr_L=L;for(n=1,testlimit,curr_n=testlimit-n+2;curr_p=(floor(curr_n^curr_L))-1;print("n is ",testlimit-n+1," ; Current prime is ",curr_p," and is_prime check = ",isprime(curr_p));curr_L=(curr_n^curr_L)-curr_p;);

There is a little correction required for the calculation of $p_1$. Depending on the $L_n$ calculated, sometimes the recovered value $\lfloor (2)^{L_{1}} \rfloor = 2$ instead of $3$. And for that reason, when the value is $2$, $f(1)=p_{1}=\lfloor (2)^{L_{1}} \rfloor - 1 = 2-1 = 1$ instead of the expected $p_1=2$. To handle this special case, we can express the prime-generating function as:

$$f(n)=p_{n}=\lfloor (n+1)^{L_{n}} \rfloor - 1 + \delta_{f(n),2}$$

Where $\delta_{f(n),2}$ is the Kronecker delta function (kindly provided by @MitchellSpector in this question). Basically it is a little trick that will assure that always $f(1)=2$ independently of the value of $\lfloor (n+1)^{L_{n}} \rfloor$ ($2$ or $3$). It would be possible a definitions-by-case of $f(n)$ as well instead of using one single expression.

This is a graph of the evolution of $L_n$ (only four decimals of precision):

enter image description here

I would like to ask the following questions:

  1. Are the calculations correct or is there a mistake in the assumptions?

  2. How could I prove that $L_n$ is decreasing in the long term and there is indeed a limit? The tests show that but I am a little bit lost about how to demonstrate that it really is decreasing (because each step depends on the gaps between primes). A hint about the starting step would be great!

  3. Initially I think this kind of recursive prime-generating function is a little bit different from the original results of Mills and towers of powers of Wright, but it might be possible that a similar idea had been explored before in recent literature. Initially I did not find such references. Are there similar solutions as the one I am devising? Any references to papers would be very appreciated. Thank you!

$\endgroup$
  • $\begingroup$ Assuming that there are infinitely many pairs of twin primes, I believe that there are infinitely many values of $m$ such that $L_{m+1}>L_m>1$, hence $\lim_{n\to\infty}L_n\neq1$ (and in general does not exist). $\endgroup$ – barak manos Sep 26 '16 at 6:45
  • 1
    $\begingroup$ A "concrete region" kinda makes the whole thing a little pointless IMO (i.e., this is by far not as "impressive" as Mills constant, for example). We all know that $\pi(n)\approx\frac{n}{\ln(n)}$, so we already have a rough idea (a "concrete region") of where the next prime is going to be... $\endgroup$ – barak manos Sep 26 '16 at 7:26
  • 2
    $\begingroup$ Well, in a nutshell (and simple words), if you look at prime distribution "from afar" (what you call "the big picture"), then it indeed looks smooth. This is a well known fact (hence the approximation that I have quoted in the previous comment). But as you zoom in, their distribution looks rather chaotic. I think that is where the prime-number "issue" lies - i.e., not in the macro level, but in the micro level. $\endgroup$ – barak manos Sep 26 '16 at 7:38
  • $\begingroup$ @barakmanos that is very right indeed, thank you for making me think! Depending on the prime gaps makes this generating function not so cool as the canonicals, because it will not have a limit, so the $lim_{n\to\infty}L_n$ version of the constant will not exist. If you have time and you can wrap-up your points in an answer I would very gladly accept it as an answer! $\endgroup$ – iadvd Sep 26 '16 at 7:44
  • $\begingroup$ @barakmanos thanks to your help I have been able to rethink the prime-representing function. The main point is forcing $L_n$ to be strictly decreasing. I have added an answer. If still you want to add your initial answer as I mentioned I will gladly accept it as the answer to the question. Regards! $\endgroup$ – iadvd Sep 26 '16 at 9:28
3
$\begingroup$

So say that for some $C\in\Bbb{R}$, we have: $$p_n\sim C^{(\log2)(n+3)}$$ Now: $$L_n\sim\dfrac{\log(C^{(\log 2)(n+3)}+L_{n-1})}{\log 2^{n+3}}$$ We already know that $L_{n-1} < 1$, while $C^{(\log 2)(n+3)}$ tends to infinity: $$L_n\sim \dfrac{\log(C^{(\log 2)(n+3)})}{\log 2^{n+3}} = \dfrac{1}{\log 2^{n+3}}\cdot \log(C^{(\log 2)(n+3)})=\\ \log(C^{\dfrac{(\log 2)(n+3)}{\log 2^{n+3}}})=\log(C^{\dfrac{(\log 2)(n+3)}{(\log 2)(n+3)}})= \log C$$ We can now say: $$L_n \sim C \Longleftrightarrow p_n \sim e^{C^{(\log 2)(n+3)}}$$ So you'll still have some Mills-like constant involved.

$\endgroup$
  • $\begingroup$ very nice! thank you for that insight! $\endgroup$ – iadvd Sep 28 '16 at 6:00
1
$\begingroup$

Thanks to @barakmanos I have been able to understand that due to the oscillating gaps between primes, the proposed constant $L_n$ will not be able to have a proper limit. To avoid that issue, I have restricted the conditions to force $L_n$ to be strictly decreasing, so a prime-generating function of this kind requires some more restrictions to have a constant with a limit when $n \to \infty$. Based on these two points:

  1. The gap between the embedded primes will be strictly increasing. The first prime selected will be $11$ then $19$ (gap 8), then 29 (gap 10), then 41 (gap 12), etc.

  2. The formula will be modified so each $n$ forces the value of $L$ to decrease on each iteration by using powers of $2$ associated to each $n$.

$$L_n=\frac{Ln(p_n+L_{n-1})}{Ln(2^{n+3})}$$

The initial status is $n=1$, $p_1=11$, $L_0=0$

So this looks like this ($16$ initial values):

enter image description here

Now $L_n$ is strictly decreasing, and a limit (rational or not) is assured.

The PARI/GP code to generate the constant:

\p20000;
testlimit=500;prev_gap=6;current_pr=11;L=0;for(n=1,testlimit,print("added prime p_",n,"=",current_pr,"; gap=",prev_gap);L=log(current_pr+L)/log(2^(n+3));prev_pr=current_pr;current_pr=nextprime(current_pr+prev_gap+1);prev_gap=current_pr-prev_pr;);print("n is ",testlimit," and L is ",L);

The constant now has this value for $n=500$:

$$L_{500}=0.0396890...$$

So in general the recursive process to recover $L_{n}$ and $f(n)=p_n$ from $L_{n+1}$ and $f(n+1)=p_{n+1}$ now will be:

$$L_{n}=(2^{n+1})^{L_{n+1}}-p_{n+1}$$

$$f(n)=p_{n}=\lfloor (2^{n})^{L_{n}} \rfloor$$

The following code, having $L_{500}$ calculates backwards the complete set of primes $\{p_{500}..p_{1}\}$

curr_L=L;for(n=1,testlimit,curr_n=testlimit-n+1;curr_p=floor((2^(curr_n+3))^curr_L);print("n = ",testlimit-n+1,"; current prime is ",curr_p," and is prime check = ",isprime(curr_p));curr_L=((2^(curr_n+3))^curr_L)-curr_p;);

Now it looks much more like a Mills-like constant but recursive!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.