Smallest positive integer that is not coprime to any member of a set of integers

[Edited]This problem is an integer linear programming problem. Let the prime factors be ${ p_i | i=1\ldots n }$, and the radicals of the input numbers be $Rad(n_k) = \prod_{i\in S_k} p_i$. The problem is then finding \begin{equation} \min \sum_i x_i \log p_i \end{equation} given the constraints $x_i \in {0,1}$ and $\sum_{i\in S_k} x_i \geq 1$.

I think this should be NP-hard, even if the prime factorisation is given.

The idea here is that given an instance of the (NP-hard) set cover problem with $n$ sets $S_1,\ldots,S_n\subset U$, you can reduce it to this problem by choosing $n$ primes $p_1,\ldots,p_n$ between $2^n$ and $2^{n+1}$, and allocating one prime to each set. Now encode each element $x\in U$ by $f(x)=\prod_{i:x\in S_i}p_i$.

A minimal set cover corresponds to a minimal-cardinality set of primes whose product has a common factor with $f(x)$ for each $x$. Also, the bounds on the primes mean that the set with minimal product (which is what you need for your problem) must also be a minimal-cardinality set.

The difficulty here is finding a suitable set of primes in polynomial time. There is certainly an algorithm to do this in polynomial expected time - pick numbers in range at random and use a polynomial-time primality test. The prime number theorem implies there are enough primes in range that you find $n$ of them after an expected polynomial number (in $n$) of tries. Whether there is a deterministic algorithm to find such a set (even assuming, say, generalised Riemann hypothesis) I don't know.

This is a wrong answer, but a better greedy algorithm than the greedy algorithms provided so far.

If $P$ is your set of primes, and $N_1,\dots,N_k$ are the sets of prime factors for each number, then define, for $p\in P$: $$m_p=|\{i\mid p\in N_i\}|$$ Then find $p_0\in P$ which minimizes $v_p=\frac{\log p}{m_p}.$

Then remove the numbers divisible by $p_0,$ and start again.

So, for example, $\{3\cdot 7,5\cdot 7,2\}$ we get $m_2=1,m_3=1,m_5=1,m_7=2.$ $p_0=7$ minimizes, and we are left with the set $\{2\}.$ We get the answer $14.$

Essentially, $v_p=\frac {\log p}{m_p}$ is the “price per unit” of choosing $p$ as the first factor.

This kind of greedy algorithm usually doesn’t work in all cases, but at least it does better than giving the wrong “value,” minimizing $\log p$ (or equivalently, just minimizing $p.$) Minimizing $\log p$ is like minimizing the cost without looking at how many units it buys.

A simple example where my algorithm doesn’t work is $\{2\cdot 7,5\cdot 7\},$ which gives $10$ when $7$ is the answer.

Another example where my algorithm doesn’t work:

$$\{3,5\}\cup \left(3\cdot 7\cdot\{p_1,\dots,p_n\}\right)\cup \left(5\cdot 7\cdot\{p_1,\dots,p_n\}\right)$$ where the $p_i>7$ are distinct primes.

$m_7=2n, m_3=m_5=n+1,$ and for large enough $n,$ $$\frac{\log 7}{2n}<\frac{\log 3}{n+1}.$$ $n\geq 8$ is enough to fail.

The key reason the greedy algorithm doesn’t work is that at the next step, the value of the primes changes.

Also, when the $N_i$ are small, we have fewer options to choose from. It might be better to find a minimum-sized $N_i,$ and find the prime in that $N_i$ which minimizes the cost. In particular, then, when some $N_i$ are singletons, we get those elements immediately, as in my complicated counterexample.

But it still doesn’t solve the case $\{2\cdot7,5\cdot7\}.$

If $p_1<p_2<p_3,$ my algorithm gives the wrong answer for $\{p_1p_3,p_2p_3\}$ when $p_1^2<p_3<p_1p_2.$ The “smallest primes” greedy algorithm gives the wrong answer whenever $p_1p_2>p_3.$ So there is a slight improvement in this case.

Maybe slightly better: For $i=1,\dots,k$ let $p_i\in N_i$ minimize $v_{p_i}$ in $N_i.$ Let $s_i$ be the second best $v_{q_i}$ in $N_i,$ or $+\infty$ if $N_i$ has only one element. Then pick the $p_i$ which maximizes $s_{i}-v_{p_i}.$

That is, pick an element from a set where the cost increase goes up the most if we don't select $p.$

Then $\{p_1\cdot p_3,p_2\cdot p_3\}$ gives $p_3$ first if $\log p_2-\log(p_3)/2 >\log(p_3)/2-\log p_1$ or if $p_1p_2>p_3.$

This algorithm fails with $$\{2\cdot 31,3\cdot 31,5\cdot 31\},$$ since $\log(31)/3-\log(2)<\log(5)-\log(31)/3,$ so my greedy algorithm chooses $31$ first.

I think that a modified Sieve of Eratosthenes works, if you assume that you already know what the prime numbers are. Instead of applying it to the natural numbers, apply it to the set of integers under analysis.

If any of the numbers in the set have $2$ as a factor, record $2$ in a save list and remove all members of the set that are $\equiv 0 \bmod 2$.

If any of the remaining numbers in the set have $3$ as a factor, note $3$ in the save list and remove all members of the set that are $\equiv 0 \bmod 3$.

Repeat for each successively larger prime. You will eventually remove every number in any finite set, and you will have a finite list of saved primes.

Edits in response to comment by OP:

Multiply the members of the list to obtain a product.

Next determine the gcd of the set of numbers, and compare it with the product just obtained.

The smaller of the product and the gcd is at least a very good candidate for the smallest number not coprime to any member of the original set. If I can tighten this up further, I will add more.