By definition, how is a prime number represented?

Question

Even numbers can be easily represented as $2n$. Odd numbers as $2n+1$. An exactly divisible operation can be defined as $n = dq$.

But, is there an specific way of representing a prime number, obtained by a proof of some sort?

Nothing useful. You may find the following article interesting. — André Nicolas, Oct 31 '13 at 21:44
There is no polynomial that will give only prime values for integers, besides constant polynomials $f(x) = p$, where $p$ is prime to begin with. — Stahl, Oct 31 '13 at 22:00
See here for a lot of information about this: http://en.wikipedia.org/wiki/Formula_for_primes
In particular you might be interested in the prime-generating Diophantine equation, and in Mills's constant. — user7530, Oct 31 '13 at 22:10
Or maybe you're looking for the notion of primality certificate (http://en.wikipedia.org/wiki/Primality_certificate). — Magdiragdag, Oct 31 '13 at 22:36

score 7 · Answer 1 · answered Nov 02 '13 at 00:28

7

From Jones, J., Sato, D., Wada, H. and Wiens, D. (1976). Diophantine representation of the set of prime numbers. American Mathematical Monthly, 83, 449-464.

The set of prime numbers is identical with the set of positive values taken on by the polynomial

$(k+2)(1-(wz+h+j-q)^2-((gk+2g+k+1)\cdot(h+j)+h-z)^2-(2n+p+q+z-e)^2-(16(k+1)^3\cdot(k+2)\cdot(n+1)^2+1-f^2)^2-(e^3\cdot(e+2)(a+1)^2+1-o^2)^2-((a^2-1)y^2+1-x^2)^2-(16r^2y^4(a^2-1)+1-u^2)^2-(((a+u^2(u^2-a))^2-1)\cdot(n+4dy)^2+1-(x+cu)^2)^2-(n+l+v-y)^2-((a^2-1)l^2+1-m^2)^2-(ai+k+1-l-i)^2-(p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m)^2-(q+y(a-p-1)+s(2ap+2a-p^2-2p-2)-x)^2-(z+pl(a-p)+t(2ap-p^2-1)-pm)^2)$

as the variables range over the nonnegative integers.

answered Nov 02 '13 at 00:28

JRN

6,566

2

Note the funny thing about the expression, it's a formula for the primes expressed as a product of two integers: $(k+2)$ and $(1-\cdots)$. (It works because the polynomial is a prime if and only if the term $(1-\cdots)$ is equal to 1, that is, if and only if the expression $\cdots$ is equal to 0.) – JRN Nov 02 '13 at 00:34
Seriously, if it wasn't on StackExchange I would take it as a joke. I've never seen that and more, never would've believed that something like that could even exist. Truly jaw-dropping, even if there actually isn't any hard math behind it... – Jeyekomon Nov 05 '13 at 17:28

score 1 · Accepted Answer · answered Nov 02 '13 at 00:15

$$P:= \{p \in \mathbb{N}: \forall c \in \mathbb{N}, (c|p \Rightarrow (c = p \lor c = 1)) \}$$

Is that what you're looking for? Or maybe you were thinking of something along the line of Euclid's Lemma...?

$$P = \{ p \in \mathbb{N} : \forall a,b \in \mathbb{N}, p|ab \Rightarrow (p|a \lor p|b) \}$$

score 1 · Answer 3 · answered Nov 02 '13 at 00:47

Rowland's formula for the primes generates only 1's and primes. (See this blog post for a discussion. The paper can be found here.)

Let $a(1)=7$ and $a(n)=a(n-1)+\gcd(n,a(n-1))$ for $n\ge 2,n\in\mathbb{N}$. Then $a(n)-a(n-1)$ is either 1 or prime.

Another formula, due to Benoit Cloitre (see this blog post), also gives only 1's and primes.

Let $b(1)=1$ and $b(n)=b(n-1)+\mathrm{lcm}(n,b(n-1))$ for $n\ge 2,n\in\mathbb{N}$. Then $b(n)/b(n-1)-1$ is either 1 or prime.

score 0 · Answer 4 · answered Nov 02 '13 at 01:39

Try an adder process based on 30n

30n+/-1 30n+/-7 30n+/-11 30n+/-13

This eliminates a large number of composites and leaves 8 columns of primes.

A little work and a lot of replication knocks the list down even more.

7*11 7*41 7*71 7*101

Etc eliminates a string of composites in the 30n-13 column again intensive but does eliminate all the composites from the list leaving only the primes.

Same with

17*23 17*53 17*83 17*113 Etc....

eliminates a string of composites in the 30n+7 column

An extensive list of all primes is need to prove a large mersennes value.

Quite a gem for smaller values if you need to determine a larger value finding which 30n column the number belongs in first simplifies the proocess significantly

By definition, how is a prime number represented?

4 Answers4

Linked