# Function to map prime numbers?
**URL:** https://boards.straightdope.com/t/function-to-map-prime-numbers/649645
**Category:** Factual Questions
**Created:** [February 7, 2013, 10:10pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645 "2013-02-07T22:10:45Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@am77494](https://boards.straightdope.com/u/am77494)
#### Post date: [February 7, 2013, 10:10pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/1 "2013-02-07T22:10:45Z")
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.)
---
### Author:  [@Asympotically\_fat](https://boards.straightdope.com/u/Asympotically_fat)
#### Post date: [February 8, 2013, 2:52am UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/2 "2013-02-08T02:52:49Z")
There are explicit formulae for the nth prime, but they’re not particularly neat (or even useful):
> **[Prime Formulas -- from Wolfram MathWorld](https://mathworld.wolfram.com/PrimeFormulas.html)**
>
> There exist a variety of formulas for either producing the nth prime as a function of n or taking on only prime values. However, all such formulas require either extremely accurate knowledge of some unknown constant, or effectively require knowledge...
I think the answer is that there’s no known useful neat formula for the primes and there probably isn’t one either.
---
### Author:  [@am77494](https://boards.straightdope.com/u/am77494)
#### Post date: [February 8, 2013, 11:18am UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/3 "2013-02-08T11:18:09Z")
Asympotically fat - thank you for the reply
---
### Author:  [@Hail\_Ants](https://boards.straightdope.com/u/Hail_Ants)
#### Post date: [February 8, 2013, 7:05pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/4 "2013-02-08T19:05:57Z")
This site, [www.UlamSpiral.com](http://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…
---
### Author:  [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)
#### Post date: [February 8, 2013, 7:14pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/5 "2013-02-08T19:14:28Z")
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.](http://en.wikipedia.org/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.
---
### Author:  [@deltasigma](https://boards.straightdope.com/u/deltasigma)
#### Post date: [February 8, 2013, 8:50pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/6 "2013-02-08T20:50:09Z")
What about generating all odd non-primes and then finding what’s missing?
---
### Author:  [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)
#### Post date: [February 8, 2013, 9:30pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/7 "2013-02-08T21:30:08Z")
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.
---
### Author:  [@Pleonast](https://boards.straightdope.com/u/Pleonast)
#### Post date: [February 8, 2013, 10:34pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/8 "2013-02-08T22:34:53Z")
> [@Hari\_Seldon](#):
>
> 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.
---
### Author:  [@filmore](https://boards.straightdope.com/u/filmore)
#### Post date: [February 8, 2013, 11:05pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/9 "2013-02-08T23:05:17Z")
> [@Hari\_Seldon](#):
>
> 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.
Why does this work? It seems very non-intuitive.
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [February 8, 2013, 11:29pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/10 "2013-02-08T23:29:58Z")
> [@filmore](#):
>
> 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
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [February 8, 2013, 11:36pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/11 "2013-02-08T23:36:33Z")
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
---
### Author:  [@filmore](https://boards.straightdope.com/u/filmore)
#### Post date: [February 9, 2013, 1:44am UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/12 "2013-02-09T01:44:34Z")
Thanks for the explanation. I get it now.
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [February 14, 2013, 7:02pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/13 "2013-02-14T19:02:25Z")
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;\
### Author:  [@SayTwo](https://boards.straightdope.com/u/SayTwo)
#### Post date: [February 15, 2013, 8:02am UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/14 "2013-02-15T08:02:05Z")
Isn’t this strongly related to Euclid’s elegant proofs of the infinity of the primes?
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [February 15, 2013, 2:06pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/15 "2013-02-15T14:06:33Z")
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.
---
### Author:  [@Asympotically\_fat](https://boards.straightdope.com/u/Asympotically_fat)
#### Post date: [February 15, 2013, 5:22pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/16 "2013-02-15T17:22:08Z")
Didn’t Euler himself have a different proof for the infinity of the primes?
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [February 15, 2013, 6:53pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/17 "2013-02-15T18:53:54Z")
> [@Asympotically\_fat](#):
>
> 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.
---
### Author:  [@filmore](https://boards.straightdope.com/u/filmore)
#### Post date: [February 15, 2013, 7:47pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/18 "2013-02-15T19:47:01Z")
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.
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [February 15, 2013, 8:05pm UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/19 "2013-02-15T20:05:52Z")
Yes.
A^(3^n). Problem is no one has a clue what A is but we do know it exists.
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [February 16, 2013, 2:03am UTC](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645/20 "2013-02-16T02:03:02Z")
An even simpler one: n^0 + 1.
[Next page](https://boards.straightdope.com/t/function-to-map-prime-numbers/649645.md?page=2)