Function to map prime numbers?

Is there proof that a function, F (n) that gives the nth prime number, cannot exist as a neat analytical function ? (I use the term neat analytical to mean a combination of the usual operators like Sigma, Sine, Cosine, multiplication, factorial, etc. etc.)

There are explicit formulae for the nth prime, but they’re not particularly neat (or even useful):

I think the answer is that there’s no known useful neat formula for the primes and there probably isn’t one either.

Asympotically fat - thank you for the reply

This site, www.UlamSpiral.com may interest you. It has a small app that generates ‘prime spirals’, an interesting facet of primes I was wholly unaware of. Being that modern PCs are as fast as supercomputers of yore it can create pretty complex stuff…

It’s well known (i.e. a few math guys know about it) that there’s no non-constant polynomial with rational coefficients that only generates primes for integer inputs.

Wiki: Formula for primes.

We know there are some constraints on such a formula if more exotic operations are allowed.

As the wiki page notes, you can convert a deterministic prime number test into a prime number generator - but this usually involves breaking the “usual analytic” operations rule from the OP.

What about generating all odd non-primes and then finding what’s missing?

I might mention that there is a simple (but not particularly useful) test for primes. The positive integer p is prime if and only if p divides 1 + (p-1)!. Not useful because factorials are so hard to calculate exactly.

Neat! I’ve not seen that before. But you need to exclude 1.

Why does this work? It seems very non-intuitive.

Because (p-2)! = 1 mod p. The proof is non-trivial but as an example take p = 7 and look at 1 x 2 x 3 x 4 x 5 and rearrange it as 1 x (2x4) x (3x5) = 1 x 8 x 15. Since 8 and 15 are 1 mod p in reduced form it is 1 x 1 x 1 mod p or 1 mod p. 1 x (p-1) is obviously -1 mod p. So what all of this means is that there exist an n such that (p-1)! = np - 1
Therefore np = (p-1)! + 1 and thus p | (p-1)! + 1

It does not works for composites beause assuming q =/= p^2 (p prime) then it can be written in the form q = mn and m =/= n and both are less than q which makes (q-1)! = 0 mod q

If q does = p^2 and p > 2 then 2p < q and thus is a factor in (q-1)! and therefore (q-1)! = 0 mod q

If q = 4 then by examination 3! = 2 mod 4

Damn edit window

  • The heart of the proof is assume A < p. Since a and p are relatively prime there exist a B : AB = 1 mod p.
    if CB = 1 mod p then CB - AB = B(C - A) = 0 mod p which means that B|p which means B = 1 which means A = C = 1. Therefore there is only one pair that uses a given number. This the numbers 2, 3, 4 . . . p-2 can be paired as to make products = 1 mod p

Thanks for the explanation. I get it now.

Oh I forgot a key point of the proof and why it is from 2 to p-2
A natural question is could you have a number n smaller than p so that n^2 = 1 mod p
Assume there were one. That means that n^2 -1 = (n + 1) (n - 1) = kp so p | (n+1) or p | (n-1)
since n;<p p | n+1 implies n = p-1 and p | n-1 implies n = 1 since p divides 0.

Isn’t this strongly related to Euclid’s elegant proofs of the infinity of the primes?

Not really.
Euclid’s proof was assume A, B and C are the only prime numbers then what divides ABC+1? It can’t be A, B or C so it must be some other prime D. Lather. Rinse. Repeat.

I’ve seen it taught as assume a largest prime N then there must be a prime > N that divides N! + 1 which looks similar to, but is not related to, Wilson’s Theorem.

Didn’t Euler himself have a different proof for the infinity of the primes?

Yes. He had a couple of proofs, one of which was that PI(p/(p-1)) diverges.

What about a variation of the OP. Is there an equation which only produces prime numbers?

It doesn’t have to produce all the primes, but whatever number it produces is prime. So maybe it prints 7, 29, 47, 113, etc. Lots of primes are skipped, but every number it produces is prime.

Yes.
A^(3^n). Problem is no one has a clue what A is but we do know it exists.

An even simpler one: n^0 + 1.