## Prim numbers formula

Is any formula that produces nth prime ?
if not visit this web site

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target
 Doesnt m=10 give 21=3*7 ??
 Recognitions: Homework Help Science Advisor 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 $\left\lfloor\lfloor x \rfloor / x \right\rfloor$. It's really nothing special.

## Prim numbers formula

Please work on this formula and find all gaps in order to fin a formula for primes

Recognitions:
Gold Member
Staff Emeritus
 Quote by morphism 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 $\left\lfloor\lfloor x \rfloor / x \right\rfloor$. It's really nothing special.
Ah, so it's just a clever way to obscure a definition by cases, and is really just saying

$$H(m) = \begin{cases} 2m + 1 & 2m + 1 \textbox{\ is\ prime} \\ 2 & \textbox{otherwise} \end{cases}$$

 Quote by morphism According to Maple, H(10)=2.
I guess you're right, I must've had an error somewhere.

Recognitions:
Gold Member
Staff Emeritus
 Quote by morphism 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 $\left\lfloor\lfloor x \rfloor / x \right\rfloor$. 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?

 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.

 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?

Recognitions:
Gold Member
Staff Emeritus
 Quote by huba 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.
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.

 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?

 Quote by Hurkyl 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.

 Recognitions: Gold Member Science Advisor Staff Emeritus Good call; I had the wrong definition of H in my head when I responded.

 Quote by hadi amiri 4 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.

Recognitions:
Homework Help
 Quote by HallsofIvy 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 $$O(\sqrt n)$$ arithmetic operations, or $$O(\sqrt n/\log n)$$ with precomputation of primes. With Newton's method and Karatsuba, this takes $$O(n^{0.8})$$ 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 $$\lfloor(2m)!/(2m+1)\rfloor$$ is noting that if 2n+1 is composite, $$\lfloor(2m)!/(2m+1)\rfloor=(2m)!/(2m+1)$$. But this is what we're trying to determine, so slower methods must prevail. Now there are methods for computing n! in $$O\left(n(\log n)^{2+\varepsilon}\right)$$ bit operations, but these require factorization of n -- again, what we want to avoid. So binary splitting gives the solution in time $$O(n^{1.585})$$, though with lots of logarithmic factors hidden in the big O.* After that the exponentiation must be performed, at cost $$O(\log n!)=O(n\log n)$$. 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?

 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

 Quote by majesticman 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.

 Tags thegreatmyth