Re: [math-fun] n is prime iff

At 04:02 PM 9/11/03, Jon Perry wrote:

[1+sum(i=1,n-1,sigma(i)*part(n-i)}]/part(n-1) = n

where part(k) is the k-th partition number.

I think that the denominator should be (part(n)-1). I can't recall having seen a characterization of primality that was less efficient than carrying out the sieve of Eratosthenes for all positive integers up to n, but that seems to be one. However, it isn't hard to do worse. For example, n is prime iff ((n-1)*n^n^n)! is not a multiple of n^n^n^n. This appears to be computationally infeasible for n > 2. -- Fred W. Helenius <fredh@ix.netcom.com>