Talk:Ramanujan prime

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

Stub Class

Low Priority

Field: Number theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Geometry guy 22:01, 11 July 2007 (UTC)

[edit] 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{align} \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{align}$

--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)

[edit] 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)

Talk:Ramanujan prime

From Wikipedia, the free encyclopedia

[edit] Algorithm

[edit] Pseudocode

Views

Navigation

Interaction

Search