Talk:Ramanujan prime

Algorithm

I see there is a minor edit war going on over whether there is an algorithm to determine whether a prime p is a Ramanujan prime. Surely it is clear that an algorithm exists ? We can test p as follows. First, find π(p)-π(p/2) - call this q. Then use upper and lower bounds on π(x) (see prime number theorem for examples) to find a monotonically increasing function f(x) such that π(x)-π(x/2) > f(x) (possibly for large enough x, but this doesn't matter). Find r such that f(r)>q, so we know that f(x)>q for all x>r. Then we have

$\pi (x)-\pi ({\frac {x}{2}})>f(x)>q{\mbox{ for all }}x>r$

Then find π(x)-π(x/2) for all integers up to r. We know that π(x)-π(x/2) cannot be less than q if x > r, so we now know all integers for which π(x)-π(x/2) is less than q, and so we know whether p is a Ramanujan prime. Not necessarily an efficient method - but it is an algorithm. Gandalf61 13:10, 6 July 2007 (UTC)

I agree an algorithm can be made. I'm not sure whether it would be considered OR to say so, but I certainly think the claim that there is no known algorithm should be removed. I already have 3 reverts so I'm not doing it. The claim was added by an IP who explicitly refuses to give a source and keeps removing {{fact}} tags. The IP has been WP:3RR warned for it at User talk:218.133.184.93#3RR, but that hasn't stopped the IP from breaking 3RR shortly after at Copeland–Erdős constant. I have been in conflict with the IP at both articles and made several reverts myself (without breaking 3RR), so I think I'm too close to report it at Wikipedia:Administrators' noticeboard/3RR. PrimeHunter 14:11, 6 July 2007 (UTC)

Well, I will wait for a while to see if anyone comes along and says "hang on, it's not that easy", and, if not, I will remove the claim that there is no known algorithm. Gandalf61 15:04, 6 July 2007 (UTC)

(after edit conflict) Here is the construction of an actual algorithm – an elementary exercise. Suppose we have some function S on the positive integers such that

$\pi (x)-\pi ({\tfrac {x}{2}})\geq n~\mathrm {for} ~\mathrm {all} ~x\geq S(n)\,.$

Since Ramanujan prime R_n is the smallest integer r satisfying

$\pi (x)-\pi ({\tfrac {x}{2}})\geq n~\mathrm {for} ~\mathrm {all} ~x\geq r\,,$

it follows that S(n) is an upper bound on R_n.

Therefore, if we have an definition of such an S that is a computable function, we can determine R_n by simply trying r = 1, r = 2, ..., r = S(n), and taking the first value satisfying the inequality. Since the sequence of Ramanujan primes is strictly increasing, we can then test any integer for Ramanujan primehood by generating the successive Ramanujan primes, and see if the last one not exceeding the given input integer is equal to it.

It remains to construct an effective upperbound S(n). From Prime counting function#Inequalities we know that

${\frac {x}{\log x+2}}<\pi (x)<{\frac {x}{\log x-4}}~\mathrm {for} ~x\geq 55\,.$

Abbreviating

$L(x):={\frac {x}{\log x+2}},~U(x):={\frac {x}{\log x-4}}\,,$

we have then:

$\pi (x)-\pi ({\tfrac {x}{2}})>L(x)-U({\tfrac {x}{2}})~\mathrm {for} ~x\geq 110\,.$

It is not hard to verify the following two auxiliary inequalities:

$L(x)\geq {\tfrac {3}{2}}U({\tfrac {x}{2}})~\mathrm {for} ~x\geq 16e^{22}\,,$

${\tfrac {1}{2}}U({\tfrac {x}{2}})>{\sqrt {x}}~~~~\mathrm {for} ~x\geq 16e^{22}\,.$

In fact, x > 2e⁴ already suffices for the latter inequality.

Now define

$S(n)=\mathrm {max} (n^{2},16e^{22})\,.$

Then, for x ≥ S(n),

${\begin{aligned}\pi (x)-\pi ({\tfrac {x}{2}})&>L(x)-U({\tfrac {x}{2}})\\&\geq {\tfrac {3}{2}}U({\tfrac {x}{2}})-U({\tfrac {x}{2}})\\&={\tfrac {1}{2}}U({\tfrac {x}{2}})\\&>{\sqrt {x}}\\&\geq n\,.\\\end{aligned}}$

 --Lambiam^Talk 15:10, 6 July 2007 (UTC)

Lambiam says "...we can determine R_n by simply trying r = 1, r = 2, ..., r = S(n), and taking the first value satisfying the inequality.". This is going the wrong way. You must work down from x = S(n) until you find x = R_n - 1 where it fails. Otherwise, you are assuming that $\pi (x)-\pi ({\tfrac {x}{2}})\!$ is a non-decreasing function (which I doubt). JRSpriggs 04:13, 7 July 2007 (UTC)

The above may be confusing the explicit "outer" loop, which has r as the running variable, and the implicit inner loop with x as its variable (implied by "for all x ≥ r"). The inequality must be tested for all values of x in the range from r up to S(n). The order in which this is done is immaterial; it may as well be done in parallel. The difference π(x) – π(x/2) is neither increasing nor decreasing, but is more likely to fail for large x. However, here we are not concerned with efficiency (and if we were, testing it for large x is more expensive). For the outer loop, we need to find the smallest value of r having the property that the inequality is satisfied (for all x ≥ r). If both r = 1234567891 and r = 1231 have that property, the answer is definitely not 1234567891. It could be 1231, unless some smaller value for r also works. To find the smallest value, the obvious approach is to test for increasing values.  --Lambiam^Talk 12:10, 7 July 2007 (UTC)

For example: To verify that R₂ = 11, we must check that π(x) – π(x/2) ≥ 2 for every x in the set {11, 12, 13, ..., about 57 000 000 000} regardless of whether we do it my way or your way. The work is the same whether we go from 11 to 57 000 000 000 or from 57 000 000 000 to 11. In my method, we check those numbers first and then we would just check that π(10) – π(5) = 4 - 3 = 1 which is not greater or equal to 2. Then we could stop and know that R₂ = 11. In your method, we would have to check for x = 1, x = 2, x = 3, x = 4, x = 5, x = 6, x = 7, x = 8, x = 9, x = 10, and then we would still have to check from x = 11 all the way to x = 57 000 000 000. So one must do additional unnecessary checking by your method, and still do all the checking which must be done by my method. JRSpriggs 01:57, 8 July 2007 (UTC)

I must confess that I don't understand your method. All you wrote initially is that we must "work down" from x = S(n) – which for small n is about 57·10⁹. The stopping criterion was not quite clear; when have we "found" x = R_n - 1? What are "those numbers" we check first in your method? Could you give the algorithm in some firm of pseudocode? Since I was only concerned with the existence of an algorithm, I haven't given any consideration to its efficiency.  --Lambiam^Talk 06:58, 8 July 2007 (UTC)

Pseudocode

If I understand your method correctly, the pseudocode for it would be:

Input n

Calculate S(n) //here is where one might hope for some great improvement

For r = 1 to S(n) do //outer loop begins

For x = r to S(n) do //inner loop begins

If π(x) – π(x/2) < n, goto failed

Endfor

Output "R_n = r"

Stop

failed: Continue

Endfor

My method would be like this:

Input n

Calculate S(n) //here is where one might hope for some great improvement

For x = S(n) to 1 do //only loop begins

If π(x) – π(x/2) < n, then

r = x + 1

Output "R_n = r"

Stop

Endif

Endfor

I am using the fact that the criterion tested depends only on x and n, not on r. So I can use all the previously checked facts for each new value of r. JRSpriggs 01:57, 9 July 2007 (UTC)

I see. These two versions are equivalent when viewed as input–output relations. You confused me by saying my method was going the wrong way, using an unwarranted assumption about a function being non-decreasing. I attempted to translate the original mathematical definition as straightforwardly as possible (the smallest integer to satisfy a certain condition), which in general tends to reduce the opportunity for introducing errors and to simplify the proof of correctness. Yours is an optimization.  --Lambiam^Talk 06:26, 9 July 2007 (UTC)

Well, at first, I did not realize that you meant to have two loops. Originally, I thought you meant it to work like this

Input n

Calculate S(n) //here is where one might hope for some great improvement

For r = 1 to S(n) do //only loop begins

If π(r) – π(r/2) ≥ n, then

Output "R_n = r"

Stop

Endif

Endfor

But then you explained that you meant to imply a loop over x. JRSpriggs 04:23, 10 July 2007 (UTC)

Number of unitary prime divisors of n!

A056171 Number of unitary prime divisors of n!. at http://www.research.att.com/~njas/sequences/A056171

Note the:

COMMENT  A unitary prime divisor for n! is not smaller than n/2. a(n)=PrimePi[n]-PrimePi[n/2] 

This means that this list of numbers are related by the fact that each R(k) is next number to the largest a(n) of some value. The largest x for which π(x) − π(x / 2) ≤ n, when x < R(n+1). For example, in A056171 a(x) = a(10) = 1 = n, so R(2) = 11.

What is the largest known Ramanujan prime? Is there a good list of over the first 1000?

You might also include a conjecture of mine:

There is at least one Ramanujan prime between each triangular number >= C(22) = 22*(22+1)/2 = 253.

This conjecture, of course, leads to the question of the growth rate of Ramanujan primes to the number of primes.

John W. Nicholson

Reddwarf2956 (talk) 04:18, 2 August 2008 (UTC)

Wikipedia content should be based on reliable sources. Has a source satisfying Wikipedia:Reliable sources published your conjecture? PrimeHunter (talk) 00:11, 13 August 2008 (UTC)

Adding a repeated reference

I don't know how to add a repeated reference. Namely, reference 7 to the section "Ramanujan prime corollary" after it was used in "Bounds and an asymptotic formula". John W. Nicholson (talk) 03:53, 6 June 2019 (UTC)

Attempted addition of "Ramanujan Prime Corollary"

@Reddwarf2956: If you believe that there is a case to be made for adding the contested content, please discuss it here. The issue is that the material is not mainstream literature because it is neither discussed nor cited in a substantial number of independent papers (in fact, none). This is not the place to include everything ever published about Ramanujan primes. — MarkH21 (talk) 08:48, 7 June 2019 (UTC)

You clearly did not read the reference 7 as stated in the above problem. Papers citing this reference 7 paper: https://scholar.google.com/scholar?cites=13654990629479404360&as_sdt=5,25&sciodt=0,25&hl=en And if you did read the paper and other papers on "Ramanujan Primes" you would realize that not "everything ever published about Ramanujan primes" is in this article.

The "Ramanujan Prime Corollary" is a equivalent statement to Ramanujan Primes (without the equals sign, which can be explained) by just using the function pi(x) and rearrangement, you can see this too. It is the same as with Bertrand's postulate which does not show the details of the equivalency also.

You have chosen to edit this article as to remove this section which as been here since 2010-11-26T14:56:41 and edited many times since then. Please make your actions productive. John W. Nicholson (talk) 14:40, 7 June 2019 (UTC)

I will respond to your claims and explain in greater detail why this material should not be in the article:

1. There is no claim that this paper contains "everything ever published about Ramanujan primes". The point is that there are standards for inclusion of content here, otherwise we would indiscriminately allow the inclusion of all publications. This is mentioned, for instance, at WP:NOTEVERYTHING and is related to WP:FRINGE. Since Wikipedia is not an indiscriminate collection of information, we must "consider a viewpoint's prevalence in reliable sources" (WP:WEIGHT) and "treat each aspect with a weight proportional to its treatment in the body of reliable, published material on the subject" (WP:PROPORTION).
2. The paper is cited 3 times, two of which are actually a single article written by the other author (and therefore not independent) and the other is a preprint (and therefore not a publication). This is a far cry from a substantial number of independent papers that would establish this result as mainstream literature. Since this material is not mentioned in any reliable independent published literature, it is not suitable for inclusion.
3. I was brought here by this WikiProject Mathematics talk section due to the concerns of Joel B. Lewis (talk · contribs) about possible original research concerns. Since you seem to be one of the authors of this paper, you have a clear conflict of interest on this subject and should not be adding this material directly to Wikipedia articles. This guide details what you should do when engaging the Wikipedia community about content that you have created.

Before making accusations against others, please reconsider the specific challenges being made to your position. — MarkH21 (talk) 23:32, 7 June 2019 (UTC)