Pressing the envelope, presumably the best scenario would be a simple proof of the Prime Number Theorem. After all, Wilson’s Theorem gives a necessary and sufficient condition, in terms of the Gamma Function, for a number to be a prime, and Stirling’s Formula specifies the asymptotic behaviour of the Gamma Function.
$\begingroup$
$\endgroup$
2
-
18$\begingroup$ You're not pressing the envelope, you're trying to stuff a watermelon into it. I am pretty sure the error in Stirling's formula for $\Gamma(n)$ is way bigger than $n$ for large $n$ no matter how many terms you include, hence your idea has no chance of going anywhere. $\endgroup$– Harald Hanche-OlsenCommented Oct 16, 2010 at 17:57
-
6$\begingroup$ @:Harald Hanche-Olsen:Your point is well taken, but poorly given. The word “envelope” here is not the postal kind, but rather means a specialized case of “boundary” (specifically, sense # 7 of the definition of “envelope” in the Merriam-Webster online dictionary). You could have appropriately said, for example, “You are not pressing the envelope, but egregiously elbowing it.” $\endgroup$– Mike JonesCommented Oct 19, 2010 at 0:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
Using Robbins' [1] form of Stirling's formula,
$$\sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n+1))< n!< \sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n))$$
we get
$$\left\lceil\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-11))\right\rceil$$ $$\le (n-1)!\le$$ $$\left\lfloor\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-12))\right\rfloor$$
which is accurate enough to distinguish prime from composite for $n\le8$. For larger numbers, the error bound is too large.
This can be extended further using a modification of Wilson's theorem: for n > 9, $$\lfloor n/2\rfloor!\equiv0\pmod n$$ if and only if n is composite. This allows testing 10 through 15, plus (with some cleverness) 17.
With tighter explicit bounds and high-precision evaluation, it might be possible to test as high as 100 with related methods: direct evaluation up to 25 and the 'divide by 4' variant of the above for n > 25.
This is not so much 'using a cannon to swat a fly' (using methods more powerful than needed) as it is 'using the space station to swat a fly': the methods must be extremely powerful and accurate to do very little.
[1] H. Robbins, "A Remark on Stirling's Formula." The American Mathematical Monthly 62 (1955), pp. 26-29.
-
2$\begingroup$ The point being that I'm already pretty good at testing primality up to $n = 100$. $\endgroup$ Commented Oct 17, 2010 at 0:24
-
5$\begingroup$ Yes, but with less than two hours of research, plus a bignum library, you could have a millisecond-scale test rather than a nanosecond-scale test! $\endgroup$– CharlesCommented Oct 17, 2010 at 3:01
-
3$\begingroup$ Remark: If you use the stronger form of Stirlings's theorem, where the trailing term is a sum over Bernoulli numbers, and you truncate that sum at the optimal point, then you can get much farther but you still lose in the end. The error is computing $n!$ this way is roughly
$n!/(\pi e^{2 \pi n} \sqrt{n})$, which is greater than $1$ once $n$ is larger than$1455 \approx e^{2 \pi +1}$. See Concrete Mathematics, Problem 9.26. $\endgroup$ Commented Oct 21, 2010 at 15:02 -
1$\begingroup$ @David: I really didn't expect to be able to get that far. With cautious modifications to Wilson's theorem that could probably give primality tests up to ten or fifteen thousand. Ah, wastefulness... $\endgroup$– CharlesCommented Oct 21, 2010 at 16:18
-
1$\begingroup$ The convergent version converges incredibly slowly. We are now swatting flies with glaciers. $\endgroup$ Commented Oct 4, 2012 at 15:39