10
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 1. By "precompute" i meant before starting brute-force algorithm. 2. Complexity of factoring is indeed subexponential, see the definiton of $C$. $\endgroup$ – SkyterX Oct 16 '15 at 19:34
  • $\begingroup$ @D.W. on point 2, the complexity of factoring is subexponential on the length of the bitstring representing the number, but SkyterX correctly says that it is $O(\sqrt{C})$, that is, proportional to the square root of the size of the number. $\endgroup$ – Lieuwe Vinkhuijzen Oct 16 '15 at 22:52
  • $\begingroup$ @LieuweVinkhuijzen, That doesn't look right to me. The complexity of factoring using GNFS will be something like $O(\exp\{1.9 (\log C)^{1/3} (\log \log C)^{2/3}\})$, which is significantly less than $O(\sqrt{C})$. See en.wikipedia.org/wiki/…. $\endgroup$ – D.W. Oct 17 '15 at 0:23
  • $\begingroup$ The statement that the second method performs better "for small $n$ and $C$" isn't quite right. It performs better only if $n \gg \sqrt{C}/\log(C)$. Thus $n$ needs to be large for the second method to perform better (not small). $\endgroup$ – D.W. Oct 17 '15 at 2:07
  • $\begingroup$ @D.W. You're right, I wasn't aware of the complexity of the GNFS. $\endgroup$ – Lieuwe Vinkhuijzen Oct 17 '15 at 11:15
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess, that any fast algorithm for this problem must include some kind of factorization of input set $S$. I will check out those factorization algorithms, but there still is a problem of properly testing them, which rises a second problem i mentioned of constructing set $S$ with maximal answer. $\endgroup$ – SkyterX Oct 17 '15 at 16:30
  • $\begingroup$ ECM finds one factor in the time you give. If all factors of a number are ≤ n log C then you need to repeat the algorithm, up to log C / log (n log C) times. $\endgroup$ – gnasher729 Oct 15 '16 at 23:02
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.