patternMinor
Least Common Non-Divisor
Viewed 0 times
divisorcommonleastnon
Problem
Basically, the problem is: For a set $S$ of positive numbers, find a minimal number $d$ that is not a divisor of any element of $S$, i.e. $\forall x \in S,\ d \nmid x$.
Denote $n = |S|$ and $C = \max(S) $.
Consider the function $F(x) = $ the least prime number not dividing $x$. It is easy to see that $F(x) \leq \log x$. And for a set $S$, let $F(S) = $ the least prime that doesn't divide any element of $S$. We have an upper bound
$$F(S) \leq F(\operatorname{lcm}(S)) \leq F(C^n) \leq n \log C.$$
Therefore a simple brute-force algorithm, which enumerates all numbers from $1$ to $n \log C$ and checks if it doesn't divide any element of $S$, is polynomial and has time complexity $O(n^2 \log C)$.
The other way to solve the problem is to compute all factors for every element of $S$ and use them in brute-force algorithm to check if $x$ is an answer in $O(1)$ time. This algorithm has time complexity $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ and uses $O(n \log C)$ memory, because we don't need to compute and store factors greater than $n \log C$. For small $n$ and $C$ it performs better.
In detail, the algorithm consists of two parts:
-
Construct a set $\hat{S}$ composed of all factors of all elements of $S$, i.e. $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$
This can be done in $O(n \cdot \min (\sqrt{C}, n \log C))$ time and $O(n \log C)$ memory. (Where does this come from? For any element of $S$, we can factor it using either trial factorization with all numbers up to $\sqrt{C}$ or all primes up to $n \log C$, whichever is smaller; thus each element of $S$ can be factored in time $O(\min (\sqrt{C}, n \log C))$ time.)
-
Find minimal number $d \notin \hat{S}$. This step requires $O(|\hat{S}|) = O(n \log C)$ time, if checking whether $x \in \hat{S}$ can be done in $O(1)$ time.
I have two questions that I'm interested in:
Denote $n = |S|$ and $C = \max(S) $.
Consider the function $F(x) = $ the least prime number not dividing $x$. It is easy to see that $F(x) \leq \log x$. And for a set $S$, let $F(S) = $ the least prime that doesn't divide any element of $S$. We have an upper bound
$$F(S) \leq F(\operatorname{lcm}(S)) \leq F(C^n) \leq n \log C.$$
Therefore a simple brute-force algorithm, which enumerates all numbers from $1$ to $n \log C$ and checks if it doesn't divide any element of $S$, is polynomial and has time complexity $O(n^2 \log C)$.
The other way to solve the problem is to compute all factors for every element of $S$ and use them in brute-force algorithm to check if $x$ is an answer in $O(1)$ time. This algorithm has time complexity $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ and uses $O(n \log C)$ memory, because we don't need to compute and store factors greater than $n \log C$. For small $n$ and $C$ it performs better.
In detail, the algorithm consists of two parts:
-
Construct a set $\hat{S}$ composed of all factors of all elements of $S$, i.e. $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$
This can be done in $O(n \cdot \min (\sqrt{C}, n \log C))$ time and $O(n \log C)$ memory. (Where does this come from? For any element of $S$, we can factor it using either trial factorization with all numbers up to $\sqrt{C}$ or all primes up to $n \log C$, whichever is smaller; thus each element of $S$ can be factored in time $O(\min (\sqrt{C}, n \log C))$ time.)
-
Find minimal number $d \notin \hat{S}$. This step requires $O(|\hat{S}|) = O(n \log C)$ time, if checking whether $x \in \hat{S}$ can be done in $O(1)$ time.
I have two questions that I'm interested in:
- Is there a faster algorithm to solve the problem?
- For given $n$ and $C$, how can w
Solution
It is possible to improve on your second algorithm by using better algorithms for integer factorization.
There are two algorithms for integer factorization that are relevant here:
-
GNFS can factor an integer $\le C$ with running time $O(L_C[0.33,1.92])$.
-
ECM can find a factors $\le n \log C$ (if any exists) with running time $O(L_{n \log C}[0.5,1.41])$; finding all factors will take $O(\log C / \log(n \log C))$ times as long (which is relatively small compared to the running time of ECM).
Here $L_n[\alpha,c] = \exp\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\}$.
That's a pretty horrendous-looking expression for the running time, but the important fact is that this is faster than the methods you mentioned. In particular, $L_C[0.33,1.92]$ is asymptotically much smaller than $\sqrt{C}$, i.e., GNFS is much faster than trying all possible factors $\le \sqrt{C}$. Also $L_{n \log C}[0.5,1.41]$ is asymptotically much smaller than $n \log C$, i.e., ECM is much faster than trying all possible factors $\le n \log C$.
So, the total running time for this method is roughly $\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$, and this is asymptotically better than your first method and asymptotically better than your second method. I don't know if it is possible to do even better.
There are two algorithms for integer factorization that are relevant here:
-
GNFS can factor an integer $\le C$ with running time $O(L_C[0.33,1.92])$.
-
ECM can find a factors $\le n \log C$ (if any exists) with running time $O(L_{n \log C}[0.5,1.41])$; finding all factors will take $O(\log C / \log(n \log C))$ times as long (which is relatively small compared to the running time of ECM).
Here $L_n[\alpha,c] = \exp\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\}$.
That's a pretty horrendous-looking expression for the running time, but the important fact is that this is faster than the methods you mentioned. In particular, $L_C[0.33,1.92]$ is asymptotically much smaller than $\sqrt{C}$, i.e., GNFS is much faster than trying all possible factors $\le \sqrt{C}$. Also $L_{n \log C}[0.5,1.41]$ is asymptotically much smaller than $n \log C$, i.e., ECM is much faster than trying all possible factors $\le n \log C$.
So, the total running time for this method is roughly $\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$, and this is asymptotically better than your first method and asymptotically better than your second method. I don't know if it is possible to do even better.
Context
StackExchange Computer Science Q#48338, answer score: 6
Revisions (0)
No revisions yet.