Let $\nu (n)$ be the number of primes less than or equal to $n$ where $n$ is a positive integer. Prove that $\dfrac{n}{\nu(n)}=k$ has a solution for every integer $k \geq 2$.

I was thinking of using the Prime Number Theorem which says $\nu(n) \sim \frac{n}{\log{n}}$, but I don't see how to apply it to the question. Is there a simpler way to solve this?

  • $\begingroup$ The usual notation is $\pi(n)$. $\endgroup$ – lhf Jun 11 '16 at 1:56
  • 1
    $\begingroup$ FWIW the sequence of $n$ such that $n/\pi(n)$ is an integer is in OEIS under A057809. $\endgroup$ – daniel Jun 11 '16 at 13:18

The PNT shows that the expression on the left will eventually exceed every $k$. Let $n_0$ be the largest $n$ for which the expression on the left is less than $k$. Then $n_0+1$ must be composite. So $n_0 < \nu (n_0) k$, but $n_0 + 1\geq \nu ( n_0 +1)k =\nu (n_0) k$. It follows that we have equality, so we're done.

| cite | improve this answer | |
  • $\begingroup$ Why must $n_0+1$ be composite? $\endgroup$ – user19405892 Jun 11 '16 at 1:21
  • 1
    $\begingroup$ Because as you increase $n$, the expression $n/\nu(n)$ will decrease when you hit a prime $n$ since the fraction exceeds 1 and you are increasing both numerator and denominator by 1 $\endgroup$ – Barry Smith Jun 11 '16 at 1:37
  • $\begingroup$ This answer seems correct but personally I would like to see "$n_0+1$ must be composite" and "[i]t follows that we have equality" explained in the answer itself. Even in the comment above the contradiction (that there would be a larger $n_0$ such that the expression on the left is less than $k$) is not stated explicitly . +1 $\endgroup$ – daniel Jun 12 '16 at 8:22

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.