5
$\begingroup$

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.

$\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$ Commented 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 Jones
    Commented Oct 19, 2010 at 0:39

1 Answer 1

37
$\begingroup$

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.

$\endgroup$
9
  • 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$
    – Charles
    Commented 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$
    – Charles
    Commented 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .