# Can Stirling's approximation be used to obtain lower and upper bound for $\pi(x)$?

The Willan's formula is given as follows (taken from Ribenboim's Little book of bigger primes): $$\pi(x)=\sum_{j=2}^{x}f(j) \text{ where } f(j)=\frac{\sin^2\left(\pi\frac{(j-1)!^2}{j}\right)}{\sin^2\left(\frac{\pi}{j}\right)}$$ And the famous Stirling's formula: $$n! \approx \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ We know that we can obtain both lower and upper bounds for $n!$ using this formula. So is it possible to apply the Striling's approximation to $(j-1)!$ in the Willan's formula - to obtain lower and upper bounds for $\pi(x)$?

• No. If we denote the approximation of $k!$ by $\alpha(k)$, then you need $\lvert (j-1)! - \alpha(j-1)\rvert < 2j$ to be able to say anything about the sine term (beyond the trivial $0 \leqslant \sin^2 x \leqslant 1$), that's much much more than Stirling's approximation gives you. – Daniel Fischer Aug 30 '15 at 12:54
• You may find mathoverflow.net/questions/42393/… interesting. – Gerry Myerson Aug 30 '15 at 13:08

Stirling's formula unfortunately has potentially big errors - the approximation does not mean that $$n! -\sqrt{2 \pi n}\left(\frac{n}{e}\right)^n\to 0,$$ only that $$\frac{n!}{\sqrt{2 \pi n}\left(\frac{n}{e}\right)^n}\to 1.$$

So an approximation of $n!$ is not of much use.

Basically, the above formula is "trivial" once you know Wilson's theorem:

$$p\text{ is prime}\iff (p-1)!+1\equiv 0\pmod p$$ and that $$p\text{is not prime}\iff (p-1)!\equiv 0\pmod p$$

That would mean a primality test could be computed by testing $(n-1)!\bmod n$, but Sterling won't do, there, either, because the approximation is not "good enough" to ensure it is within $1$ of $(n-1)!$.

Specifically, $$n!=\sqrt{2 \pi n}\left(\frac{n}{e}\right)^n + O\left(\sqrt{2\pi (n-1) }\left(\frac{n-1}{e}\right)^{n-1}\right)$$

That's a big room for error - basically, a constant times $(n-1)!$. You'd need an approximation that was within $1/2$ for $n$ large enough (to distinguish $-1$ and $0$.)

• What about this one: $$n! \approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1+\frac{1}{(2^1)(6n)^1}+{1\over(2^3)(6n)^2}-{139\over(2^3)(2\cdot3\cdot5)(6n)^3}-{571\over(2^6)(2\cdot3\cdot5)(6n)^4} + \cdots \right).?$$ Regardless of complexity... Does it suffice? – VanDerWarden Aug 30 '15 at 14:10
• No. What is $n! -\sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$ in that approximation? It approaches infinity, but you'd need it bounded below $1/2$ for it to be useful. How could that be useful, then? If you computed that formula out to $n$ terms, you might get a good approximation, but it is hard to imagine how that could be more useful than the usual method of calculating $n!$. And, it is not easy to see how to compute the main term $(n/e)^n$ in a particularly quick way, given that you need an abitrary-precision $e$. – Thomas Andrews Aug 30 '15 at 14:30
• Using this will never be faster nor more memory-efficient than just using, say, the Sieve of Eratosthenes to find all primes $n<x$. – Thomas Andrews Aug 30 '15 at 14:33
• Essentially, Willan is just a mathematical joke. It's not wrong, per se, it's just sort of pointless - using Wilson's theorem to create a silly "formula" for $\pi(x)$. – Thomas Andrews Aug 30 '15 at 14:34
• In particular, there is nothing about $f(x)=\sin^2(\pi x)$ that is necessary here, other than $f(0)=0, f(1+x)= f(x)$ for all $x$, and $f(x)\neq 0$ when $x=\frac{1}{n}$ for $n>1$ an integer. – Thomas Andrews Aug 30 '15 at 14:45