1
$\begingroup$

I need to solve the non-linear equation $n/ \ln(n) = 990,000$, which is the approximation of the $990,000$th prime number. This is what I tried:

$n = 990,000 ( \ln (n)) $ (Multiply both sides by $\ln(n)$)

$\frac{n}{990,000} = \ln(n)$

$e^{n/990,000} = e ^ {\ln(n)}$

$n = e^{n/990,000}$

So then I went here: https://primes.utm.edu/nthprime/index.php#nth

And found the 990,000 prime number is: $15,318,907$

So I plugged that in for n:

$990, 000\text{th prime} = e^{15,318,907/990000}$

$15,318,907 \neq 3803815.32$

But clearly the numbers are not equal, I'm not sure what I've done wrong, or how to go about getting an approximate answer for $n$, I need to find the answer mathematically using that formula.

$\endgroup$
3
  • $\begingroup$ $e^{15,318,907/990000}$ is not even close to $3803815.32$, it's more of a $5249500$. Anyway if you check the approximation before you took the exponential ($15318907/990,000 \approx \ln 15318907$) you can see it works quite well. Just the error increases after exponentiation... $\endgroup$
    – Sil
    Feb 9, 2018 at 23:44
  • $\begingroup$ Also, notice that you can use the prime number theorem to derive approximation formula for $n$-th prime (proofwiki.org/wiki/Approximate_Value_of_Nth_Prime_Number). $\endgroup$
    – Sil
    Feb 9, 2018 at 23:58
  • $\begingroup$ From comments on the answers, this is a case of the XY problem. You want an approximation to the nth prime (see this question: Is there a way to find the approximate value of the nth prime?). But your question is about a single potential solution. $\endgroup$
    – DanaJ
    Feb 11, 2018 at 8:17

3 Answers 3

Reset to default
2
$\begingroup$

The solution to the equation ${n \over \ln n} = b$ is the Product Log or Lambert's W function, so for this problem $n\to -990000\ W_{-1}\left(\frac{-1}{990000}\right) \approx 1.64497 10^7$. The 990000th prime (found by common computer search) is $15318907 \approx 1.53 \times 10^7$.

$\endgroup$
5
  • $\begingroup$ how did you go from 1.644 ^ 7 to 1.53 * 10 ^ 7? $\endgroup$
    – 0xI
    Feb 9, 2018 at 23:48
  • $\begingroup$ As in, how did you figure out the prime number here. Did I miss a step in your solution? $\endgroup$
    – 0xI
    Feb 9, 2018 at 23:48
  • $\begingroup$ I didn't go from $1.644 \times 10^7$ to $1.53 \times 10^7$. The solution to the nonlinear equation is merely an approximation. Of course no formula gives an exact value for a prime. (Whoever found such a formula would win a Field's Medal and change mathematics forever.) $\endgroup$
    – David G. Stork
    Feb 9, 2018 at 23:50
  • $\begingroup$ So How would I get 1.53 x 10^7 if I didn't know the answer was 15318907?How would I find the approximate answer myself, without knowing the answer is 15318907. $\endgroup$
    – 0xI
    Feb 9, 2018 at 23:51
  • $\begingroup$ @rrrrrr, there are a variety of ways. Inverting the Riemann R function (e.g. binary search with R) is the most accurate -- it gives 15318519 for your example, which is quite close. You can also invert li (the logarithmic integral) with or without a second sqrt(n) term. You can average the upper and lower bounds from Dusart 2010, Axler 2013, or Axler 2017. You can use the Cipolla 1902 asymptotic formula. $\endgroup$
    – DanaJ
    Feb 11, 2018 at 8:12
1
$\begingroup$

$n/\ln(n)=990,000$ is not a approximation of the 990,000th prime number!

If you define the function $\pi(n)$ which gives the number of primes less than or equal to $n$, then $$ \pi(n)\sim \frac{n}{\ln(n)}$$

$\endgroup$
7
  • $\begingroup$ How do I find the prime number using that function? $\endgroup$
    – 0xI
    Feb 9, 2018 at 23:46
  • $\begingroup$ Why do you think you can? $\endgroup$
    – fleablood
    Feb 9, 2018 at 23:46
  • $\begingroup$ Because my assignment says I need to using n/ln (n) :/ $\endgroup$
    – 0xI
    Feb 9, 2018 at 23:47
  • $\begingroup$ You assignment says to actually find the 990,000th prime number???? $\endgroup$
    – fleablood
    Feb 9, 2018 at 23:49
  • $\begingroup$ Yep, we have to find it using that formula or a formula that's more efficient. $\endgroup$
    – 0xI
    Feb 9, 2018 at 23:50
1
$\begingroup$

The prime counting function $\frac {n}{\ln n}$ says that there are about $\frac {n}{\ln n}$ prime numbers less than $n.$

so if you have say that there are $990,000$ prime numbers less than 15 odd million

Then we would hope to see that $\frac {15,318,907}{\ln (15,308,907)} \approx 990,000$

In fact:

$\frac {15,318,907}{\ln (15,308,907)} \approx 925,916$ giving about 7% error.

Which ties out with this table.

https://en.wikipedia.org/wiki/Prime-counting_function

$\endgroup$
1
  • $\begingroup$ How do I get the 15million without using that site? I need to find the number using the formula, or some other formula. $\endgroup$
    – 0xI
    Feb 9, 2018 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.