Find $n$ such that $n$ does not divide any integer in the set

Question

You are given a set of integers $\{a, b, c, d, e, f, g, \ldots\}$. Find the minimum $n$ that does not divide any number of the set.

This is a programming problem, but I am looking for a mathematical solution.

Answer 1

Let the set be $A = \{ n_1, \ldots, n_N \}$, where the elements $n_i$ are sorted in ascending order. Let $P(n)$ be true, if and only if $n \in \mathbb{N}$ does not divide any element of $A$. So $n>1$. The task is to find a minimal $n$ with that property $P$ true for $A$.

Each number $n_i$ uniquely factorizes into $$ n_i = p_1^{e_1} p_2^{e_2} \cdots $$ where $p_k$ is the $k$-th prime number and the exponent is a non-negative integer.

Its divisors aside from $1$ are products of its prime factors (those prime numbers with non-zero exponents) with exponents such that these do not exceed the $e_i$.

A candidate for a solution $n$ must not be a divisor for any $n_i$. So it can not be any of the occuring prime factors.

The smallest prime number $p$ not occurring is not a divisor to any $n_i$.

As Ruben pointed out, another upper bound is $n_N+1$. The set $\{ 2,4\}$ prefers $p=3<4+1=5$, the set $\{ 2,3\}$ prefers $n_2+1=4<5$.

Up to this point we can limit the solution to $$ B = \{ 2, \ldots, \min(p, n_N+1) \} $$

If there is a number $n$ smaller than $p$, which would do the job, it itself must be a product of prime numbers, each of these smaller than $p$.

So how can we combine those prime factors such to keep $P$ true?

One could try a prime factor with exponent one larger than it showed up in the $n_i$. For $\{ 2,3,6 \}$ it would give $2^{1+1}=4$ and $3^{1+1}=9$ where $4$ beats $p=5$ and $6+1=7$ as upper bounds.

A practical problem is to decide when to invest the effort determining the prime factors.

Answer 2

I don't see any nice solution. You only need to check primes and prime powers as possible answers, but that is not much of a savings. If $6$ were to not be a divisor of some number, either $2$ or $3$ is already not a divisor.

Answer 3

An trivial algorithm would be to just test for each natural number $k \geq 2$ if it divides any of the numbers in the list. This algorithm runs in ($O(m^2)$, where $m$ is the biggest number from the set), assuming that checking for divisibility takes constant time (which is not true for big enough integers). Note that $m + 1$ is always a solution, since a divisor $d$ of $n$ always satisfies $d \leq n$. $m + 1$ is the solution when the set is $\{ 2, 3, 4, ..., m - 1, m \}$. It is not true that the solution needs to be a prime (unless you require $\gcd(s, n) = 1$ for the solution $s$ and all $n$ in the set).

function answer(set S)
    for each 1 < k < m + 2
        isdivisor = false
        for each n in set S
            if k divides n
                isdivisor = true
                break (exit from inner for loop)
        if not(isdivisor) return k

In practice, it looks like the running time will depend mainly on the answer, and will be approximately linear in it.

More abstract, if we write the set as $\{ n_1, ..., n_m \}$ and write $n_j = \prod^\infty_{k = 1} p_{k}^{q_{j,k}} $ where $p_k$ is the kth prime number, the solution we seek is a sequence $l_1, l_2, ...$ with $\forall j \in [1, ..., m]$ $\exists t$ $l_t > q_{j, k}$ which minimizes $ s = \prod^\infty_{k = 1} p_k^{l_k} $.

I'm still thinking about a more efficient algorithm based on this description and Eratosthenes' sieve, but I don't think there is a particularly nice one. It is not hard to give bounds on the solution. We have $2 \leq s \leq m + 1$ and $s \leq p_k^w$, where $w = 1 + \max_{j \in \mathbb{N}} q_{j, k}$ for each prime $p_k$.