# Prime Numbers

First, the function is just that: f(n) = the nth prime number, if n is a positive integer, and undefined otherwise.

But there are probably a good half dozen or dozen closed form versions of that formula, based on things like Wilson's Theorem. None of them are particularly interesting.
http://mathworld.wolfram.com/PrimeFormulas.html
Can you list any functions F(n) = the nth prime number that will gve an answer independently of the determination of all lower primes?

Also, can you give a function P(n) which gives a 1 or 0 depending upon whether n is prime or not that in effect does not depend upon the calculation or n! or of all primes less than the square root of 'n'?

If yes to either question, please cite relevant descriptive material.

CRGreathouse
Homework Helper
Can you list any functions F(n) = the nth prime number that will gve an answer independently of the determination of all lower primes?

Also, can you give a function P(n) which gives a 1 or 0 depending upon whether n is prime or not that in effect does not depend upon the calculation or n! or of all primes less than the square root of 'n'?

I don't understand what you mean by "function", since functions don't rely on things like the determination of primes or the calculation of n!. f(n) = 2 * n! does not rely on the calculation of n!; it's just a map from 1 to 2, 2 to 4, 3 to 12, 4 to 48, etc.

Do you mean an algorithm? One algorithm for calculating 2 * n! would be n!*2; another would be prod(k=1,n,k)+prod(k=1,n,k); another would be prod_primes(p=2,n,f(p,n)), f(p,n) = 0 for n < p, f(p,n) = 2*floor(n/p)+f(p,floor(n/p)) for n >= p. The first two seem to use the factorial; the third doesn't seem to use it (but it uses a function which may seem related).

Do you mean a closed-form formula? In that case, what do you consider a closed-form formula? If you were as restrictive as "polynomial" there would be no such functions; for broader definitions, there may be. Further, it's not clear what it means for a closed-form formula to be independent of the determination of smaller primes: this is a restriction on an algorithm, not a formula. A formula is just a string of symbols along with rules for putting them together and calculating with them.

Do you mean something other than "function", "algorithm", and "closed-form formula"?

Some formulas are 'covert sieves'. For example.
$$f(n) = \prod_{k = 2}^{ \lfloor \sqrt n \rfloor } (n - k \lfloor {n \over k} \rfloor )$$​
produces a 0 if n is composite, and a non-zero if n is prime.

Hi!
Can you list any functions F(n) = the nth prime number that will gve an answer independently of the determination of all lower primes?

Also, can you give a function P(n) which gives a 1 or 0 depending upon whether n is prime or not that in effect does not depend upon the calculation or n! or of all primes less than the square root of 'n'?

If yes to either question, please cite relevant descriptive material.

Something like:
$$L_n=L_{n-2}+L_{n-3}$$ with $$L_0=0, L_1=2, L_3=3$$
also called the Perrin sequence.