Finding the size of the smallest subset with GCD = 1

Question

This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this problem anywhere.

The problem is: Given a set of $N$ distinct positive integers not greater than $10^9$, find the size $m$ of the smallest subset that has no common divisor other than 1. $N$ is at most 500, and a solution can be assumed to exist.

I managed to show that $m \le 9$. My reasoning is: Suppose there exists a minimal subset $S$ of size $|S|=10$, with gcd = 1. Then all 9-subsets of $S$ must have gcd > 1. There are exactly 10 such subsets, and their gcds must be pairwise coprime. Let these gcds be $1 < g_1 < g_2 < ... < g_{10}$, where $\gcd(g_i,g_j)=1$, for $i \neq j$. Then the maximum number in $S$ is $g_2g_3...g_{10}$. But $g_2g_3...g_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 > 10^9$, a contradiction.

However, even with this, a straightforward brute force is still too slow. Does anyone have any other ideas?

Answer 1

This problem is equivalent to the following, and it's trivial to construct reduction both ways.

Given a list of bit vectors, find the minimum number of them such that and all of them result the $0$ bit vector. $(*)$

Then we show set cover reduces to $(*)$. By set cover, I mean given a list of sets $S_1,\ldots,S_k$, find the minimum number of sets that covers their union.

We order the elements in the sets to be $a_1,\ldots,a_n$. Let $f(S) = (1-\chi_{a_1}(S),\ldots,1-\chi_{a_n}(S))$, where $\chi_x(S) = 1$ if $x\in S$, 0 otherwise. Note this function is a bijection so it has a inverse.

Now, if we solve $(*)$ on $f(S_1),\ldots,f(S_k)$, and the solutions is $\{ f(S_{b_1}),\ldots,f(S_{b_m})\}$, then $\{ f^{-1}(S_{b_1}),\ldots,f^{-1}(S_{b_m})\}$ is the solution to set cover.

Thus I would think this problem is testing one's ability to prune the search space.

Answer 2

It's possible to solve this relatively efficiently by computing all pairwise gcd's, removing duplicates, and then recursing. It's the act of removing duplicates before you recurse that makes it efficient.

I'll explain the algorithm in more detail below, but first, it helps to define a binary operator $\otimes$. If $S,T$ are sets of positive integers, define

$$S \otimes T = \{\gcd(s,t) : s \in S, t \in T\}.$$

Note that $|S \otimes T| \le |S| \times |T|$ and $|S \otimes T| \le 10^9$ (in your problem); typically, $S \otimes T$ will be even smaller than either of those bounds suggest, which helps make the algorithm efficient. Also note that we can compute $S \otimes T$ with $|S| \times |T|$ gcd operations by simple enumeration.

With that notation, here is the algorithm. Let $S_1$ be the input set of numbers. Compute $S_2 = S_1 \otimes S_1$, then $S_3 = S_1 \otimes S_2$, then $S_4 = S_1 \otimes S_3$, and so on. Find the smallest $k$ such that $1 \in S_k$ but $1 \notin S_{k-1}$. Then you know that the size of the smallest such subset is $k$. If you also want to output a concrete example of such a subset, by keeping back-pointers you can easily reconstruct such a set.

This will be relatively efficient, as none of the intermediate sets grows in size above $10^9$ (in fact, their size will probably be much smaller than that), and the running time requires about $500 \times (|S_1| + |S_2| + \cdots)$ gcd operations.

Here is an optimization that might improve efficiency even further. Basically, you can use iterated doubling to find the smallest $k$ such that $1 \in S_k$. In particular, for each element $x \in S_i$, we keep track of the smallest subset of $S_1$ whose gcd is $x$ and whose size is $\le i$. (When you remove duplicates, you resolve ties in favor of the subset that is smaller.) Now, rather than computing the sequence of nine sets $S_1,S_2,S_3,S_4,\dots,S_9$, we instead compute the sequence of five sets $S_1,S_2,S_4,S_8,S_9$, by computing $S_2 = S_1 \otimes S_1$, then $S_4 = S_2 \otimes S_2$, then $S_8 = S_4 \otimes S_4$, then $S_9 = S_1 \times S_8$. As you go, find the first $k \in [1,2,4,8,9]$ such that $1 \in S_k$. Once you've found $k$ such that $1 \in S_k$, you can immediately stop: you can find the smallest subset whose gcd is $1$ by looking at the subset associated with $1$. So, you can stop as soon as you reach a set $S_k$ such that $1 \in S_k$, which allows you to stop early if you find a smaller subset.

This should be time-efficient and space-efficient. To save space, for each element $x \in S_k$, you don't need to store the entire set: it's enough to store two backpointers (so the two elements of $S_i,S_j$ that you took the gcd of, to get $x$) and optionally the size of the corresponding subset.

In principle, you can replace the sequence $[1,2,4,8,9]$ by any other addition chain. I don't know whether some other addition chain will be any better. The optimal choice might depend upon the distribution of correct answers and the expected sizes of the sets $S_k$, which is not clear to me, but can probably be derived empirically through experimentation.

Credits: My thanks to KWillets for the idea of storing a subset of numbers along with each element of $S_i$, which allows stopping early.

Answer 3

Perhaps it is faster looking at this in another way... the largest prime less than $\sqrt{10^9}$ is 31607, for a total count of 3401 primes between 2 and 31607, not a very large number. Write each of the numbers you are given fully factored over the primes up to 31607: $$ a_i = p_1^{n_{i 1}} p_2^{n_{i 2}} \ldots P_i $$ Here $P_i$ is 1 or a large prime. Then a set of the $a_i$'s is relatively prime if the corresponding $n_{i j}$ vectors are linearly independent (and their $P$s are different or both 1), and you are looking for the rank of a matrix.

Answer 4

If you are able to find a subset with gcd(S) = 1, then I can always remove redundant elements from the subset till only 2 elements remain , which have gcd(S) = 1. Therefore, I can claim that either the smallest subset will contain 2 elements or it will not exist.

Now, we use recursion to solve this problem. Let's divide the array of numbers into 2 parts, one with n-1 elements and one with 1 element (last element). Either the 2 numbers will be in the first n-1 elements or one element will be there from 1st part paired with last element. Therefore, we are able to solve this problem in

T(n) = T(n-1) + O(n) time. which means T(n) = O(n^2).