Prime Number Formulas: Find the Nth Prime

In summary, this conversation is discussing whether formula produces nth prime. The expert says that Maple says that H(10)=2. Trial division and Newton's method are faster than this formula.
  • #1
hadi amiri 4
98
1
Last edited by a moderator:
Physics news on Phys.org
  • #2
Doesnt m=10 give 21=3*7 ??
 
  • #3
According to Maple, H(10)=2.

If you look at the formula closely, you'll notice that H(m) is going to be an odd prime whenever 2m+1 is a prime, and otherwise it's going to be 2. This follows from Wilson's theorem (2m+1 is a prime iff (2m)! + 1 = 0 (mod 2m+1)) and the behaviour of [itex] \left\lfloor\lfloor x \rfloor / x \right\rfloor[/itex]. It's really nothing special.
 
  • #4
Please work on this formula and find all gaps in order to fin a formula for primes
 
  • #5
morphism said:
According to Maple, H(10)=2.

If you look at the formula closely, you'll notice that H(m) is going to be an odd prime whenever 2m+1 is a prime, and otherwise it's going to be 2. This follows from Wilson's theorem (2m+1 is a prime iff (2m)! + 1 = 0 (mod 2m+1)) and the behaviour of [itex] \left\lfloor\lfloor x \rfloor / x \right\rfloor[/itex]. It's really nothing special.
Ah, so it's just a clever way to obscure a definition by cases, and is really just saying

[tex]H(m) = \begin{cases}
2m + 1 & 2m + 1 \textbox{\ is\ prime} \\
2 & \textbox{otherwise}
\end{cases}[/tex]
 
  • #6
morphism said:
According to Maple, H(10)=2.

I guess you're right, I must've had an error somewhere.
 
  • #7
morphism said:
According to Maple, H(10)=2.

If you look at the formula closely, you'll notice that H(m) is going to be an odd prime whenever 2m+1 is a prime, and otherwise it's going to be 2. This follows from Wilson's theorem (2m+1 is a prime iff (2m)! + 1 = 0 (mod 2m+1)) and the behaviour of [itex] \left\lfloor\lfloor x \rfloor / x \right\rfloor[/itex]. It's really nothing special.
Are you saying then that one can test whether an odd number is prime by calculating this? Wouldn't that be faster than, say, trial division by primes less than its square root?
 
  • #8
As long as (2m)! can be calculated (although it should be difficult for larger values of m), there is no need for the proposed formula, because Wilson's theorem already tests primality: if 2m+1 divides (2m)!+1 then 2m+1 is prime.
When (2m)! is difficult to calculate then the formula becomes difficult as well.
 
Last edited:
  • #9
Please work on this formula and find all gaps in order to fin a formula for primes

Using Hurkyl's definition for H(m),

H(m)=2 if 2m+1 is composite.
H(4) = 2, and for all k, H(4+3k)=2.
H(12)=2, and for all k, H(12+5k)=2,
H(24)=2, and for all k, H(24+7k)=2, etc.

This is Eratosthenes' sieve, and I know about one exact formula for primes which utilizes it: Riemann's solution for the prime counting function. What other formula can be found?
 
  • #10
huba said:
Using Hurkyl's definition for H(m),

H(4) = 2, and for all k, H(4+3k)=2.
H(12)=2, and for all k, H(12+5k)=2,
H(24)=2, and for all k, H(24+7k)=2, etc.
:confused: Why would you think any of those claims are true? Did you actually try to evaluate them for any value of k?

This is Eratosthenes' sieve,
Sure doesn't look like it.
 
  • #11
The range of H is
{3,5,7,2,11,13,2,17,19,...}={2,3,5,...}
so there is no problem.am I right?
 
  • #12
Hurkyl said:
:confused: Why would you think any of those claims are true? Did you actually try to evaluate them for any value of k?


H(m) = 2 if 2m+1 is composite.

When m = 4 + 3k, then 2m + 1 = 3(2k + 3) which is composite for all k. In fact, 3(2k + 3) gives all odd numbers > 9 that are divisible by 3.

Similarly for m = (p^2-1)/2 + pk where p is prime, because then 2m + 1 = p(2k + p), and so 2m+1 is composite, and so H(m) = 2.
 
  • #13
Good call; I had the wrong definition of H in my head when I responded.
 
  • #14
hadi amiri 4 said:
The range of H is
{3,5,7,2,11,13,2,17,19,...}={2,3,5,...}
so there is no problem.am I right?


The formula is interesting (it has certainly attracted many responses in a short time), but it does not produce the nth prime as effectively suggested in the first entry in this thread.
For a given n, we don't know for what value of m we get H(m) = the nth prime, until finding it by trial and error by calculating H(m) for a certain range of m. For instance, if the first prime is 2 (n=1), we find it (first) when m=4.
 
  • #15
HallsofIvy said:
Are you saying then that one can test whether an odd number is prime by calculating this? Wouldn't that be faster than, say, trial division by primes less than its square root?

Trial division on n takes [tex]O(\sqrt n)[/tex] arithmetic operations, or [tex]O(\sqrt n/\log n)[/tex] with precomputation of primes. With Newton's method and Karatsuba, this takes [tex]O(n^{0.8})[/tex] bit operations. Without pecomputation, this method takes only logarithmic space -- log n space for n, log n space for the calculation, and 1/2 log n space for a counter.

A quick way to calculate [tex]\lfloor(2m)!/(2m+1)\rfloor[/tex] is noting that if 2n+1 is composite, [tex]\lfloor(2m)!/(2m+1)\rfloor=(2m)!/(2m+1)[/tex]. But this is what we're trying to determine, so slower methods must prevail. Now there are methods for computing n! in [tex]O\left(n(\log n)^{2+\varepsilon}\right)[/tex] bit operations, but these require factorization of n -- again, what we want to avoid. So binary splitting gives the solution in time [tex]O(n^{1.585})[/tex], though with lots of logarithmic factors hidden in the big O.* After that the exponentiation must be performed, at cost [tex]O(\log n!)=O(n\log n)[/tex]. The space requirement for a literal computation is huge: [log]O(\log (2n)!)=O(n\log n)[/tex], an order of magnitude larger than trial division.

In conclusion, trial division is far superior, taking roughly the square root of the time and the logarithm of the space of this method.

* At several points I'm able to hide logarithmic factors between lg 3 = 1.58496... and the 1.585 I display; sneaky, eh?
 
  • #16
guys if you all were able to generate a formula that gives the nth prime...you will be rich!...correct me if i am wrong but aren't security for top secret files as well as e-commerce based on the fact that really big prime numbers (they are set as encryption keys) cannot be factorized. So good luck...i thnk it is RSA algorithm that relies on prime numbers
 
  • #17
majesticman said:
guys if you all were able to generate a formula that gives the nth prime...you will be rich!...correct me if i am wrong but aren't security for top secret files as well as e-commerce based on the fact that really big prime numbers (they are set as encryption keys) cannot be factorized. So good luck...i thnk it is RSA algorithm that relies on prime numbers

While I doubt you would get rich(If you were thinking about the RSA factorization prizes, I'm sorry to tell you, but they stopped giving them out in 2007), but you would secure your place in history.
Yes, the RSA uses prime numbers to encrypt. SSL uses prime numbers as well. If some smart guy(or gal) figures out the distribution of prime numbers those would be dropped pretty quickly.
 
  • #18
majesticman said:
guys if you all were able to generate a formula that gives the nth prime...you will be rich!
There already exist explicit formulas for the n-th prime, and a variety of algorithms for computing the n-th prime.

correct me if i am wrong but aren't security for top secret files as well as e-commerce based on the fact that really big prime numbers (they are set as encryption keys) cannot be factorized..
I should hope not -- I can factor such numbers in my head, no matter how big they are.
 
  • #19
patrcik said:
figures out the distribution of prime numbers
It's already known. The primes occur precisely when we have an integer that is not a multiple of smaller integers. :tongue: Aside from that obvious fact, there are bewildering array of bulk statistics known about the primes, and a great many more that are consequences of the Riemann hypothesis.
 
  • #20
Why is the mathematical world so focused on prime numbers, why not the general case, to find all numbers with n prime factors?
 
  • #21
majesticman said:
guys if you all were able to generate a formula that gives the nth prime...you will be rich!...correct me if i am wrong but aren't security for top secret files as well as e-commerce based on the fact that really big prime numbers (they are set as encryption keys) cannot be factorized. So good luck...i thnk it is RSA algorithm that relies on prime numbers

1. There are lots of formulas that generate primes; creating a new one won't guarantee that you can get a paper published, much less than make you rich.
2. Many encryption algorithms rely on the hardness of factoring large semiprimes; factoring primes is, of course, trivial.
 
  • #22
Kurret said:
Why is the mathematical world so focused on prime numbers, why not the general case, to find all numbers with n prime factors?

I don't think there's any push to find (general) prime numbers -- there are too many -- but to learn how to quickly factor a number into its prime factors. This is interesting because such a factorization is unique (up to order and units), though there is still interest in factoring into coprimes and partial factorization in general.
 
  • #23
Kurret said:
Why is the mathematical world so focused on prime numbers, why not the general case, to find all numbers with n prime factors?

CRGreathouse said:
I don't think there's any push to find (general) prime numbers -- there are too many -- but to learn how to quickly factor a number into its prime factors. This is interesting because such a factorization is unique (up to order and units), though there is still interest in factoring into coprimes and partial factorization in general.

That's a good question, Kurret (IMHO), and that's a good reply, Greathouse (IMHO).

Kurret,

A few more thoughts, adding to what Greathouse said.

One reason there is a "focus" on "prime numbers" these days is the relation with the Riemann hypothesis. For example, if we can show that the error term in the prime number theorem grows at the order of the square root of n, then we will know that the Riemann Hypothesis is true. (ref: Barry Mazur's "error term" article in this issue of the BAMS; the equivalence was shown about 100 years ago).

So, this fact reduces your question to "why is there so much interest in the Riemann hypothesis"?

Well, first of all, the RH is a very old problem.
Second, if it is true, many intereesting and beautiful facts about nature will follow. (My viewpoint is that interesting mathematics describes interesting things about nature.)
Third, everything that is known about the RH gives the impression that we a re very close to solving it.
Fourth, it's been that way for about 100 years now, so why haven't we solved it? (Riemann even wrote down an exact formula for the error term in the prime number theorem. It would seem that all we have to do is analyze that formula.)
Fifth, numerical studies of the behavour of the zeroes of the zeta function on the critical line indicate that current techniques are inadequate to solve it. The behaviour of those zeroes is just too strange and too sbutle to get a handle on. Therefore, a solution would likely result in a significant advance in our understanding of mathematics in general.
Sixth, there is a million dollar prize for the person who resolves it.
Seventh, the name of the person who solves it is very likely to go down in history for a very long time.

On the other hand, as Greathouse pointed out, the question you ask is really of very high interest to today's mathematicians. One reason for that is IF we could find an effectgive algorithm to answer your question, THEN we would be a lot closer to finding an effective algorithm to factoring the product of two large primes in a short period of time. This would break RSA cryptography. It is highly likely that the proof would carry over to break discrete logarithm cryptography. It is quite possible that the proof would allow us to break elliptic curve cryptography.

The underlying mathematical meta-principle that you are touching on is that it is a lot easier to ask hard questions than it isw to ask "good" quesitons. A "good" question is a question that we have a hope of solving; that we feel that if we worked on it, we should be able to come up with something.

A small group of very good mathematicians are currently investigating the properties of numbers that are the product of a large number of small primes. The fact that that investigation is difficult (but doable) underlines just how hard the question that you ask probably is.

Another good example of a "hard" question is the question of whether or not there are an infinite number of Mersenne primes. For that one, there even exists a heuristic argument that there are an infinite number and it yields an asympototic estimate for how many there are!

And yet, as far as I know, nobody has any idea about how to get started on actually proving that there are an infinite number of them. Richard Guy also said this in his book "Open Problems in Number Theory" or something like that.

Oh, oh, oh, except the female star of the science fiction movie called "Proof." The "science fiction" in the movie is that she resolved the question about the finiteness of the Mersenne primes.

DJ

P.S. I welcome corrections, or even "that doesn't sound right" comments. That's how I learn.
 
Last edited:
  • #24
I have good news the discoverer of this formula is going to publish a book that contains many results like defining the set of twin prime numbers a formula about producing nth prime and many other top results .
 
  • #25
hadi amiri 4 said:
I have good news the discoverer of this formula is going to publish a book that contains many results like defining the set of twin prime numbers a formula about producing nth prime and many other top results .

Well twin primes are old, at least as old as Sophie Germain (early 1800s) and probably older. I don't know hold long we've had explicit formulas for generating the primes, rather than just algorithms, but surely more than a hundred years.

What, then, are these "other top results"?
 
  • #26
hadi amiri 4 said:
I have good news the discoverer of this formula is going to publish a book that contains many results like defining the set of twin prime numbers a formula about producing nth prime and many other top results .

You're kidding, right? :confused:
 
  • #27
why you don not respect others attempt
have you seen this book
why you are so judgemental
 
  • #28
hadi amiri 4 said:
why you don not respect others attempt
have you seen this book
why you are so judgemental
If you don't want people evaluating your hype, then don't post it. What else are we supposed to do with it? :tongue:
 
  • #29
There is certainly no point in making qualifying statements about a claim that has not been presented in the necessary detail.
 
  • #30
hadi amiri 4 said:
why you don not respect others attempt
have you seen this book
why you are so judgemental

We haven't seen the book, that's why I asked what the "other top results" were. It's hard to respect results you don't know about.
 
  • #31
I assume you guys are being sarcastic right?

There is no formula (function) which, given an arbitrary input will guarantee a prime output, let alone, give you the primes in order.

You can work recursively, (ie, the sieve of Eratosthanes) but its not really a formula, it just knocks out the composites one prime factor at a time.

Nor has it been proven (conclusively) that there are an infinitude of twin primes.
 
  • #32
thompson03 said:
I assume you guys are being sarcastic right?

If you mean my post #25, I was not being sarcastic at all. If not, which posts were you referring to?

thompson03 said:
There is no formula (function) which, given an arbitrary input will guarantee a prime output, let alone, give you the primes in order.

MathWorld cites Ruiz 2000:
Ruiz, S. M. "The General Term of the Prime Number Sequence and the Smarandache Prime Function." Smarandache Notions J. 11, 59-61, 2000.

[tex]p_n=1+\sum_{k=1}^{2(\lfloor n\ln n\rfloor+1)}\left[1-\left\lfloor\sum_{j=2}^k1+\lfloor s(j)\rfloor}/n\right\rfloor\right][/tex]

where
[tex]s(j)=-\frac{\sum_{s=1}^j\left(\lfloor j/s\rfloor-\lfloor(j-1)/s\rfloor\right)-2}{j}[/tex]There are many more examples, some simpler and some more complex. Some give all primes in order, some give all distinct primes, some give the count of primes through n, etc.

thompson03 said:
Nor has it been proven (conclusively) that there are an infinitude of twin primes.

No one on this thread has made that claim.
 
  • #33
f(x) = x ; if x is prime does too

let me rephrase,

there is no function that is not based on recursion or more fundamentally on a sieve process.

Making a function that step by step knocks out the composites is not exactly what I meant.

"My bad" on the linguistics there, sorry
 
  • #34
thompson03 said:
let me rephrase,

there is no function that is not based on recursion or more fundamentally on a sieve process.

I suppose then that you'd consider Wilson's Theorem to be essentially a sieve?
 
  • #35
I'm not trying to be stupid, i really think this is a semantic / linguistic confusion, not an argument.

Looks to me like wilsons theorem is a test, not a function.


But, anything with factorials, list all previous values (factors).
So the Smarandache Prime Function essential shows that if you list out all of the numbers multiplied together, then there are sufficient factors to generate every number up to the current number, so if its prime, then the test holds.

straight from wolframs site:
/quote
For example, the number 8 does not divide 1!, 2!, 3!, but does divide 4!=4·3·2·1=8·3, so mu(8)=4
/endquote

So mu(5) will be 5 because 5 is prime, because none of the previous factors give multiples of five,
this is essentially saying f(x) = x is prime, if x is prime

All I mean is, there is no function F(M)=P for some input M that guarentees P is prime, and M is any single valued input, be it real, integer, complex or quaternian. If there where, it would be bloody famous and there'd be no need for prime testing algorithms. Especially if it was an invertable function!

But think of it, if you had such a function and you wanted to test if a REALLY BIG NUMBER was prime. You start plugging in inputs whose outputs are close to your REALLY BIG NUMBER until you get the result. It wouldn't even have to be a continuous function, just ordered.

So I think i am using a much more limited definition of function than you are. The sieve of eratothanes can be written in function form, but its still the sieve

Any formula that uses Sigma summation (sorry, havn't used tex in years, forgot syntax) is an algorithm, which I agree, there are lots of. And they run through countless computations to generate only a few outputs, thus making them inneffective for very large primes

I have a nice algorithm that uses the symmetry of p# and it makes the computer find primes very quickly, but it is not a function. (if your interested i'll show you, i'd like to know if its well known or perhaps something that hasn't been investigated too much anyway)

Hope this clarifies
 
<h2>1. What is a prime number?</h2><p>A prime number is a positive integer that is only divisible by 1 and itself.</p><h2>2. What is the Nth prime number?</h2><p>The Nth prime number refers to the prime number that appears in the Nth position in the sequence of prime numbers. For example, the 4th prime number is 7, as it is the 4th number in the sequence of prime numbers (2, 3, 5, 7).</p><h2>3. What is the formula for finding the Nth prime number?</h2><p>There is no single formula for finding the Nth prime number. However, there are various algorithms and methods that can be used to efficiently find prime numbers, such as the Sieve of Eratosthenes and the Sieve of Atkin.</p><h2>4. How do I use a prime number formula to find the Nth prime number?</h2><p>To use a prime number formula to find the Nth prime number, you will need to input the value of N into the formula and follow the steps outlined in the formula. This may involve using a computer program or manually calculating the result.</p><h2>5. Are there any limitations to using prime number formulas to find the Nth prime number?</h2><p>Yes, there are limitations to using prime number formulas. These formulas may only work for a certain range of numbers or may not be able to accurately find very large prime numbers. Additionally, some formulas may be more complex and time-consuming to use, making them less practical for finding large prime numbers.</p>

1. What is a prime number?

A prime number is a positive integer that is only divisible by 1 and itself.

2. What is the Nth prime number?

The Nth prime number refers to the prime number that appears in the Nth position in the sequence of prime numbers. For example, the 4th prime number is 7, as it is the 4th number in the sequence of prime numbers (2, 3, 5, 7).

3. What is the formula for finding the Nth prime number?

There is no single formula for finding the Nth prime number. However, there are various algorithms and methods that can be used to efficiently find prime numbers, such as the Sieve of Eratosthenes and the Sieve of Atkin.

4. How do I use a prime number formula to find the Nth prime number?

To use a prime number formula to find the Nth prime number, you will need to input the value of N into the formula and follow the steps outlined in the formula. This may involve using a computer program or manually calculating the result.

5. Are there any limitations to using prime number formulas to find the Nth prime number?

Yes, there are limitations to using prime number formulas. These formulas may only work for a certain range of numbers or may not be able to accurately find very large prime numbers. Additionally, some formulas may be more complex and time-consuming to use, making them less practical for finding large prime numbers.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
760
Replies
5
Views
312
  • Programming and Computer Science
Replies
22
Views
633
  • Linear and Abstract Algebra
Replies
3
Views
774
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
285
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • General Math
Replies
7
Views
1K
Replies
8
Views
262
  • Linear and Abstract Algebra
Replies
2
Views
990
Back
Top