Least Common Non-Divisor

Question

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:

1. 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.)

2. 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:

1. Is there a faster algorithm to solve the problem?
2. For given $n$ and $C$, how can we construct a set $S$ with maximal least common non-divisor?

Answer 1

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.

Answer 2

The least common non-divisor may be as large as N log C, but if the N numbers are randomly distributed then the least common non-divisor is probably a lot smaller, probably a lot less than N. I'd build tables of which primes are divisors of which numbers.

For each prime number p we have an index $k_p$ which means all numbers up to that index have been examined for divisibility by p, and we have a list of all of those numbers which were divisible by.

Then for d = 2, 3, 4, ... we try to find a number divisible by d, or show there is none. We take the largest prime factor p of d. Then we check all numbers that were divisible by p whether they are also divisible by d. If none are found, then we check further numbers with indices > $k_p$ for divisibility by p, updating $k_p$ and the list of numbers divisible by p, and checking if each number is divisible by d.

To check if there is a number divisible by p, we check on average p numbers. Later if we check if there is a number divisible by 2p, there's a 50% chance that we need to check only one number (the one that is divisible by p), and a 50% chance for checking on average 2p more numbers. Finding a number divisible by 3p is quite likely fast and so on, and we never check more than N numbers for divisibilty by p, because there are only N numbers.

I would hope this works out with about $N^2 / log N$ divisibility checks.

PS. How large would the result be for random numbers?

Assume I have N random numbers. Probability that one of N numbers is divisible by d is 1 - (1 - 1/d)^N. I assume the probability that each of the numbers 1 ≤ d ≤ k is a factor of one of the random numbers is calculated by multiplying these probabilities (Ok, that's a bit dodgy, because these probabilities are likely not quite independent).

With that assumption, with N = 1000, there's a 50% chance that one of the numbers 1..244 doesn't divide any number, and one in a billion that every number up to 507 divides one of the numbers. With N = 10,000 there's a 50% chance that one of the numbers 1..1726 doesn't divide any number, and one in a billion that every number up to 2979 divides one of the numbers.

I would propose that for N random inputs, the size of the result is a bit larger than N / ln N; maybe something like N / ln N * (ln ln N)^2. Here's why:

The probability that at least one of N random numbers is divisible by a random d is $1 - (1 - 1/d)^N$. If d is around N, then $1 - (1 - 1/d)^N$ is about 1 - exp (-1) ≈ 0.6321. That's for a single divisor; chances that each of several numbers d ≈ N is a divisor of at least one of N numbers are quite slim, so the maximum d will be significantly smaller than N.

If d << N, then $1 - (1 - 1/d)^N ≈ 1 - exp (-N / d)$.

If d ≈ N / ln N then $1 - exp (-N / d) ≈ 1 - exp (- ln N) = 1 - 1/N$.

We would add these probabilities for about N / ln N values d, but for most d the result will be significantly larger, so the largest d will be somehow larger than N / ln N but significantly smaller than N.

PS. Finding a number divisible by d:

We pick the largest prime factor p of d, and then we first examine the numbers that were already known to be divisible by p. Say d = kp. Then on average we only check k numbers that are divisible by p while checking this particular d, and we check at most all N values for divisibility by p overall, for all d divisible by p. Actually, we most likely check less than N values for most primes p, because after checking all N values the algorithm most likely ends. So if the result is R, then I expect less than N values being divided by each prime less than R. Assuming R ≤ N, that's about N^2 / log N checks.

PS. Running some tests

I ran this algorithm a few times with N = 1,000,000 random numbers > 0. The least common non-divisor was between 68,000 and 128,000 with the huge majority of runs between 100,000 and 120,000. The number of divisions was between 520 million and 1800 million which is a lot less than (N / ln N)^2; the majority of cases used between 1000 and 1500 million divisions.