Question

proof of nth prime formula

Answer 1

the \(n\)th prime \(p_n\) is given by :
\[p_n = 1+\sum\limits_{k=1}^{2^n} \left\lfloor \sqrt[n]{\dfrac{n}{1+\pi(k)}}\right\rfloor\]

where \(\pi(x) \) = number of primes not exceeding \(x\)

Answer 2

I know it is a pretty useless formula. I am just trying to prove the formula...
Do you know how to prove it or got any nice references for the proofs ?

Answer 3

I found the formula from here
http://mathworld.wolfram.com/PrimeFormulas.html

Answer 4

it kinda looks like a geometric relationship with the nth root thing

Answer 5

geometric mean stuff coming in for these number of primes

Answer 6

what i know is -> \(n^{th}\) prime can be written like this-

\(\large p_n=p_1.p_2.p_3....p_{n-1}+1\)
\[p_n=\prod_{i=1}^{n-1}p_i+1\]
so basically we need to prove that the part under the sigma notation is nothing but the product of \(1^{st}\) n-1 primes

Answer 7

what noo it cant xD

Answer 8

No Qwerty you are wrong smh

Answer 9

that might be or not be a prime, but it is not that nth prime

Answer 10

yeah that expression cannot be a prime because it is even

Answer 11

well it is still odd because there is a 2 which is a prime in there

Answer 12

that expressionj is from the euler thing to show infinite prime

Answer 13

or euclid i forgot who showed that

Answer 14

Oh, right!

Answer 15

i am lost

Answer 16

u lost me with that ec-word

Answer 17

this expression-
\(\large p_n=p_1.p_2.p_3....p_{n-1}+1\) ??

it has to be a prime because (B there is no factor of it except 1 and itself

can u write this expression in factored form?

Answer 18

right, it is a prime, but it cannot give the nth prime

Answer 19

\(p_3 = 2*3+1 = 7\)

is wrong

Answer 20

oh yeah i get your point
like we cannot get 13 and more yeahh

Answer 21

it doesnt haev to even be a prime technically be cause say the product is huge... there can be other primes not considered that might factor it

Answer 22

true, i should really think before typing haha

Answer 23

(2*3*5*7*11*13*17*19)+1=9699690+1
there are so many primes inbetween we didnt see

Answer 24

ahh hehe i do it all the time its fun

Answer 25

lol danny you have a different idea of fun dan most of us do XD JJKJKJK I do calculus problems when i am bored..........is dat weird?

Answer 26

It isn't weird, calculus is so much fun

Answer 27

: ) I love you ganeshie :p u made feel un-weird XD

Answer 28

Wilson's theorem :
\(\dfrac{(n-1)!+1}{n}\) is an integer if and only if \(n\) is a prime.

Answer 29

Using above theorem, we can express \(\pi(x)\) as
\[\pi(n) = \sum\limits_{k=2}^{n}\cos^2\pi\dfrac{(k-1)!+1}{k}\]

Answer 30

dan it will be prime
suppose \(\large p_n=p_1.p_2.p_3....p_{n-1}+1\)
suppose its not a prime and it has some prime factors then that factor must divide this expression
lets call that factor as -> \(p_{\alpha}\)
\(p_{\alpha}\) is clearly smaller than \(p_n\) and thus it will come into that expression like this somewhere- \(\large p_n=p_1.p_2.p_3..p_{\alpha}..p_{n-1}+1\)

now \(p_{\alpha}\) must divide \(p_n\) so-
\[\large p_n=\underbrace{\frac{p_1.p_2.p_3...p_{apha}.p_{n-1}}{p_{\alpha}}}+\frac{1}{p_{\alpha}}\] \(p_{\alpha}\) will divide this

but \(p_{\alpha}\) will not divide 1

so it has no prime factors thus \(p_n\) is prime

Answer 31

That doesn't work

you're assuming that your expression gives the \(n\)th prime, which is wrong.

Answer 32

oh okay i get ur point completely now

Answer 33

here is a counterexample
http://www.wolframalpha.com/input/?i=factor+2*3*5*7*11*13%2B1

Answer 34

We can only say this :

the expression \(p_1.p_2.p_3....p_{n-1}+1\) is not divisible by any of the primes \(p_1, p_2, \ldots, p_{n-1}\).

Answer 35

I was thinking since we are using \(\pi(n)\) instead of trying to figure it out I was thinking maybe I could just use this to come up with my own prime function since it has all the information we need.

I came up with this _almost_ formula.
\[f(n) = (n+1)^{\pi(n)-\pi(n-1)} -1\]

It doesn't really give the nth prime, instead it essentially takes the backwards difference \(\Delta \pi(n)\) which is 1 if n is prime and 0 if n isn't prime.

So really f(n) is equal to n if n is prime and it's equal to 0 if it's not prime. Or simpler, I could have written it as:

\[f(n) = n^{\Delta \pi(n)} \]
Where f(n)=n when n is prime and 1 otherwise. Clearly this sorta thing isn't just for primes, we could have something like \(s(n)\) which counts the number of Fibonacci numbers less than n instead of \(\pi(n)\) and then f(n) either equals a Fibonacci number or 1.

---

My other attempt as something similar, but also didn't quite work, it ends up just regenerating the same prime counting function haha:

\[\pi(n) = \sum_{k=1}^n \frac{1-(-1)^{\Delta \pi(n)}}{2}\]

Example:
remember \(\Delta \pi(n) = \pi(n)-\pi(n-1)\),

\[\pi(4) = \frac{1-(-1)^{\Delta \pi(1)}}{2} + \frac{1-(-1)^{\Delta \pi(2)}}{2} + \frac{1-(-1)^{\Delta \pi(3)}}{2}+ \frac{1-(-1)^{\Delta \pi(4)}}{2} \]
\[\pi(4) = \frac{1-(-1)^{0}}{2} + \frac{1-(-1)^{1}}{2} + \frac{1-(-1)^{1}}{2}+ \frac{1-(-1)^{0}}{2} \]
\[\pi(4) = 0+1+1+0 = 2\]

Anyways, just some fun ideas in trying to recreate the formula that end up seeming to really just be more or less specific cases of functions that describe arbitrary sequences. Heh. I'll keep playing with this original problem though.

Answer 36

Very interesting! In the nth prime formula, \(\pi(n)\) is defined as :
\[\pi(n) =\sum\limits_{k=2}^{n}\cos^2\pi\dfrac{(k-1)!+1}{k} \]

which is as useless as the actual nth prime formula. it is just another version of wilson's theorem. doesn't tell us anything new...

Answer 37

Does this work ?
\[\pi(n) = \sum\limits_{k=1}^n \frac{1-(-1)^{\Delta \pi(n)}}{2} =\sum\limits_{k=1}^n \Delta \pi(n) \]

Answer 38

Ahh telescoping !

Answer 39

I feel all these so called formulas for nth primes/prime counting are just expressing the problem in sum notation. They are not really formulas... They are not reducing any effort hmm

Answer 40

I am confused on how to read this formula, for the characteristic function of the prime numbers.
http://mathworld.wolfram.com/images/equations/PrimeFormulas/Inline23.gif

the formula comes from this page
http://mathworld.wolfram.com/PrimeFormulas.html

There are two types of brackets, and the outer one looks like floor, the inner one I am not sure

Answer 41

Oh right, we need the outer to be floor so that we get 0 when cos^2 is not 1 :

\[\pi(n) =\sum\limits_{k=2}^{n}\left\lfloor\cos^2\pi\dfrac{(k-1)!+1}{k} \right\rfloor\]

Answer 42

the inner bracket is just a bracket, like a parenthese

Answer 43

i got confused, some people use that as a floor symbol as well :)

Answer 44

by the way i found this interesting formula
$$ \large p_n=1+\sum_{r=1}^{2^n}\left\lfloor \sqrt[n]{n}-\sqrt[n]{\sum_{s=1}^{r}\left(\cos\left(\pi\frac{(s-1)!+1}{s}\right)\right)^2}\right\rfloor$$

Answer 45

Yeah, baiscally \(\dfrac{(k-1)!+1}{k}\) is integer only when \(k\) is a prime

therefore \(\cos^2 \pi \dfrac{(k-1)!+1}{k} \) evaluates to \(1\) when \(k\) is a prime and it evaluates to something between 0 and 1 when \(k\) is composite

Answer 46

i see, thats using wilson's theorem

Answer 47

Your formula looks interesting! it looks like a simplified version..

Answer 48

yes. though, if we could find a computationally simple formula,
it would render encryption obsolete

Answer 49

true haha
http://www.wolframalpha.com/input/?i=Table%5B%5Csum%5Climits_%7Bk%3D0%7D%5E%7B2%5En%7Dfloor%28+%28%5Cdfrac%7Bn%7D%7B1%2BPrimePi%28k%29%7D%29%5E%281%2Fn%29%29%2C+%7Bn%2C1%2C10%7D%5D

Answer 50

nice :)

Answer 51

I neglected to post the link from which I obtained that formula.
http://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime