0
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel Fischer Aug 30 '15 at 12:54
  • $\begingroup$ You may find mathoverflow.net/questions/42393/… interesting. $\endgroup$ – Gerry Myerson Aug 30 '15 at 13:08
2
$\begingroup$

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$.)

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – VanDerWarden Aug 30 '15 at 14:10
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Aug 30 '15 at 14:30
  • $\begingroup$ Using this will never be faster nor more memory-efficient than just using, say, the Sieve of Eratosthenes to find all primes $n<x$. $\endgroup$ – Thomas Andrews Aug 30 '15 at 14:33
  • $\begingroup$ 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)$. $\endgroup$ – Thomas Andrews Aug 30 '15 at 14:34
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Aug 30 '15 at 14:45

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.