is prime? in Operations Research

Question

Is there a way to linearize is prime? in Operations Research?

is prime(n) being true if $n$ is a prime number or false otherwise.

If it is not possible, which I suspect, is there any other way in either:

• Non linear programming
• Constraint programming

An upper bound of $n$ is known in advance, being any positive natural number.

Answer 1

TLDR: Enumerate (in advance) all primes $\le$ upper bound on $n$. Check to see whether a variable (declared as integer) equals one of the enumerated primes.

Details: Declare $x$ as integer.

Let $U$ be the upper bound on $x$.

Let $P$ be an $m$ by 1 vector consisting of all primes $\le U$.

Declare $b$ as an $m$ by 1 vector of binary variables.

$x$ is constrained to be prime by $$x = b^TP$$ $$\Sigma b = 1$$

Edit: I am answering the interpretation of the question that a variable being prime (or not prime) is a constraint in an optimization or feasibility problem. Some other answers interpret the question as formulating an optimization problem whose solution determines whether a number is prime.

Answer 2

In Mixed-Integer Linear Programming, one could consider "prime" as a new type of variables in addition to "continuous", "binary", "integer", "semi-continuous"... Then the algorithm would branch as long a as a variable of type "prime" is not prime in the relaxation. For example if a "prime" variable $x$ has value $4$ in the relaxation, then the algorithm could branch on $x$ with one branch $x \le 3$ and the other $x \ge 5$.

It also seems possible to consider this type of variables in Constraint Programming.

But as far as I know, no MILP or CP solver supports this.

Answer 3

Primality is difficult to check as it requires a statement like "there don't exist two natural numbers $a,b>1$ such that $n=a\cdot b$" which for flexible a $n$ require quantifiers to express. Quantified Mixed Integer (Linear) programming exists as a concept but I am not really aware of any solvers that can solve such problems.

This means we need to somehow "unroll" all possibilities such an quantifier would cover. Let $N$ be the upper bound of $n$ a naive one would be $\prod_{x \in \mathbb{P}} (n-x) = 0$ or some other polynomial. Other primality tests such as the Wilson test $(n-1)!\ \equiv\; -1 \pmod n$ can also be expressed but would result in even higher order polynomials.

Another alternative not using products of variables is to use the absolute value $\forall_{x\in\mathbb{P}\leq N} |n-x| \leq N b_p$ and $\sum_{x\in \mathbb{P}} b_p = 1$ and $b_p$ is a boolean. One could cut the number of equations almost in half by checking divisibility by 2.

There are more compact is prime checks and one could systematically search those for some fixed $N$. This would likely be possible using a two level Mixed Integer Quadratic problem where you try to find an constraint matrix $A \in \mathbb{R}^{n+2\times n+2}$ and a constraint vector $b \in \mathbb{R}^{n}$ that satisfies $$\forall m\in\mathbb{N}\leq N: A x \leq \begin{bmatrix} m \\ \text{isprime}(m) \\ b_1 \vdots \\ b_{n} \end{bmatrix}$$ where the parent tries to find a such a matrix $A$ and an assignment $x \in \mathbb{R}^a \times \mathbb{B}^{N-a}$ that satisfies this and the $N$ sub problems (each has it's own $m$) try to find counter examples $x$ such that for the $A,b$ from the parent problem $$A x \leq \begin{bmatrix} m \\ 1-\text{isprime}(m) \\ b_1 \vdots \\ b_{n} \end{bmatrix}$$ This counter example can then be used to add a new constraint to the parent problem. If the parent problem becomes unfeasible a bigger $n$ for the dimensions needs to be chosen. Note that only the parent problem is quadratic. If all subproblems are infeasible you found a constraint which encodes is prime. Depending how you chose $n$ and whether the parent problem has an appropriate objective it might also be the smallest $n$, a sparse $A$ or have other properties you want and can express in quadratic programming.

Note that Mixed Integer solvers are generally not great in finding feasible solutions a more different approach would be to pick a binary encoding of $n$ to be tested and do a similar find counter example make more constraints loop with a Pseudo boolean or a SAT solver. This will result in binary constraints which can then also be used in a MILP problem. Quantified boolean solvers also exist and there might be a way to "coax" them into finding a solution without bouncing back and forth. Another alternative on that front are Binary Decision Diagrams which are also use to reduce logic in computer chips.

Getting good results using either method with some analysis of the result would probably be worth publishing a paper about. There might be some other way to derive such a look up table however i am not aware of any.

Answer 4

Since primes only have $2$ divisors, $1$ and the number itself, you could use the following program to determine if an integer $n \in \mathbb{N}$ is prime or not : $$ \max \; x $$ \begin{align} \mbox{subject to }\quad n &= x \cdot y \tag{1} \\ x &\in \mathbb{N} \cap [0,n-1] \tag{2}\\ y &\in \mathbb{N} \cap [0,n] \tag{3} \end{align}

With constraints $(1)-(3)$, you try to decompose $n$ as a product of two integers $x$ and $y$, where $x$ cannot equal $n$. The objective function maximizes $x$. So if the largest $x$ you can find equals $1$, then $n$ is prime. Otherwise it is not.

For example, if $n:=10$, the following solution is optimal: $x=5$, $y=2$. So $n$ is not prime. If $n=11$, the following solution is optimal: $x=1$, $y=11$. So $n$ is prime.

Of course this is not linear, but you can easily linearize the product, and you will have a problem with binary and integer variables that determine if a number $n$ is prime or not.