3
$\begingroup$

Can someone help me to figure out what $$\lim_{n\to\infty} \frac {c_n}n-\frac{c_n}{p_n}-\frac {c_n}{n^2}$$ is equal to? I am pretty sure its $1$ and i tried many different things but i couldnt figure it out. $c_n$ is the nth composite number excluding $1$ and $p_n$ is the nth prime number. This limit is equal to $$\lim_{n\to\infty} c_n\frac {\gamma(n)}{n^2}$$ where $\gamma(x)$ is equal to how many numbers less or equal to $x$ are composite. Its kinda the inverse function of $c_n$

$\endgroup$
  • $\begingroup$ Is $c_n$ the $n$th composite number? $\endgroup$ – Arthur Aug 21 at 16:50
  • $\begingroup$ I am assuming that $c_n$ and $p_n$ denote the nth composite and prime number respectively? And 1 is not included, I'm assuming. $\endgroup$ – Gabe Aug 21 at 16:50
  • $\begingroup$ @Gabe Im sorry, i totally forgot to include that. Yeah you are right $\endgroup$ – Kinheadpump Aug 21 at 16:57
  • $\begingroup$ Have you tried plugging in the basic asymptotics $p_n\approx n\log n$, $c_n\approx n/(1-\log n)$? $\endgroup$ – Steven Stadnicki Aug 21 at 17:14
  • $\begingroup$ In particular, the first term goes to 1 and the second and third terms both go to 0 by relatively straightforward asymptotic results. $\endgroup$ – Steven Stadnicki Aug 21 at 17:17
3
$\begingroup$

Let $p(x) = \frac{x}{\ln x}$, being the approximate prime counting function. That means there are approximately $\frac{x}{\ln x}$ primes less than or equal to x, and $x-\frac{x}{\ln x}$ composites less or equal to than x.

First, let's derive $p_n$. Since there are about $\frac{x}{\ln x}$ primes less than or equal to x, there are x primes less than or equal to $x\ln(x)$. So $p_n \sim n\ln n$. Now for $c_n$, there are $x(1-\frac{1}{\ln x})$ composites less than or equal to x, so there are x composites less than or equal to $\frac{x\ln x}{(\ln x) - 1}$. Therefore, $c_n \sim \frac{n\ln n}{(\ln n) - 1}$

So, your limit now becomes: $\frac{n\ln n}{n(\ln (n) - 1)} - \frac{1}{(\ln n) - 1} - \frac{n\ln n}{n^2(\ln (n) - 1)}$, and as n approaches infinity, the last two terms drop to zero, and a simple coefficient test shows the first term is equal to one. And, $$\lim_{n\to\infty} \frac {c_n}n-\frac{c_n}{p_n}-\frac {c_n}{n^2} = 1$$

$\endgroup$
  • 1
    $\begingroup$ Please use $\sim$ not $= \ $. Moreover you don't need the PNT that $\pi(x) = o(x)$ is enough to show $\lim_{n\to\infty} \frac {c_n}n-\frac{c_n}{p_n}-\frac {c_n}{n^2} = 1$ $\endgroup$ – reuns Aug 21 at 18:13
  • $\begingroup$ Yes, thank you that is what I meant. $\endgroup$ – Gabe Aug 21 at 20:05
1
$\begingroup$

$$\frac{(2m)!}{m!^2}={2m \choose m} \ge \prod_{m < p \le 2m} p, \qquad {2^{k+1} \choose 2^k}\le 8 {2^k \choose 2^{k-1}}, \qquad \prod_{p \le n} p \le \prod_{k \le \log_2(n)+1} {2^k \choose 2^{k-1}} \le 4^{4n}$$ If $\pi(n) \ge Cn$ then $\prod_{p \le n} p \ge q^{Cn-q}$ thus for $n$ large enough we must have $\pi(n) < Cn$ which means $$\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$$ Whence $\lim_{n \to \infty} \frac{c_n}{n} = 1,\lim_{n \to \infty} \frac{c_n}{p_n} = \lim_{n \to \infty} \frac{n}{p_n} =0$ and $$\lim_{n\to\infty} \frac {c_n}n-\frac{c_n}{p_n}-\frac {c_n}{n^2} = 1-0-0$$

$\endgroup$

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.