14
$\begingroup$

Equivalently: given a list of numerators, find the lowest common denominator such that all the fractions formed can be simplified by cancellation.

Or: given a list of whole numbers, what's the smallest whole number that shares a common factor, greater than 1, with each of them? (Not necessarily the same factor shared with each member of the list.)

Clearly the given list cannot contain $\pm 1$ or no such number can be found! But for example, given $$\{8, 12, 45, 49\} = \{2^3, 2^2 \times 3, 3^2 \times 5, 7^2 \}$$ it is clear our desired number must include $2$ and $7$ in its prime factorisation, or else it will be coprime with $8$ and $49$. The fact $2$ is a factor guarantees a common factor with $12$ too, so we only need to ensure there is a common factor with $45 = 3^2 \times 5$ and this can be done most cheaply by incorporating a factor of $3$ in our prime factorisation. So the smallest number that does what we want is $2 \times 3 \times 7 = 42$, and indeed we find the greatest common divisors (highest common factors) are $\gcd(42, 8) = 2$, $\gcd(42, 12) = 6$, $\gcd(42, 45) = 3$ and $\gcd(42, 49) = 7$, so all greater than one. Alternatively, we observe that we can cancel down each of the fractions $\frac{8}{42} = \frac{4}{21}$, $\frac{12}{42} = \frac{2}{7}$, $\frac{45}{42} = \frac{15}{14}$ and $\frac{49}{42} = \frac{7}{6}$.

Does this procedure or function have a name? As a "lowest common non-coprime number" (though I can find no search engine hits under this name or close variants) it seems very closely related to the "lowest common multiple". Indeed, an obvious way to find a number that shares a factor with each member of the list is to just take

$$\operatorname{lcm}(8, 12, 45, 49) = 17640 = 2^3 \times 3^2 \times 5 \times 7^2$$

but this is clearly unnecessarily big. For starters, there's no need to raise the primes to a power — to ensure a common factor, each prime need only appear once. Dropping the unnecessary powers (i.e. taking the radical or square-free kernel — the largest divisor that is not, itself, divisible by a square number other than one) we get $2 \times 3 \times 5 \times 7 = 210$ but this is still not the smallest possible, since the prime factor $5$ wasn't required.

So what I want isn't the LCM, or even the radical of the LCM (or equivalently, the LCM of the radicals). In fact it's clear a good first step to simplify the problem would have been taking the radicals of all the numbers in our list, since the numbers sharing a factor with each of $\{2, 6, 15, 7\}$ are precisely the numbers sharing a factor with each of $\{8, 12, 45, 49\}$. Even then, it doesn't look like there's going to be a really neat algorithm to solve the problem. Consider:

$$\{2 \times 5, 3 \times 5, 2 \times 5\ \times 19 \} \text{ versus } \{2 \times 7, 3 \times 7, 2 \times 7 \times 19 \}$$

In the former case we can just use $5$ and a little thought shows it cannot be beaten; in the latter case, $7$ works but $2 \times 3 = 6$ is smaller. It seems we cannot avoid experimenting with different subsets of the prime factors to find the optimal answer. Nevertheless, the notion of a "lowest common non-coprime" function does seem interesting enough to crop up in some Math SE questions and I would like to know if mathematicians have given it a name, and whether there is an efficient algorithm (particularly if the list has already been given in prime-factorised form) for calculating it.

$\endgroup$
9
  • 2
    $\begingroup$ List all the prime factors, and it is a product of a subset of these primes. I wouldn’t be surprised if this was NP-complete, even if you are given the prime factorizations. $\endgroup$ Oct 6, 2021 at 23:49
  • 2
    $\begingroup$ It can be stated as a graph theory problem. Given a bipartite graph between two sets $S$ and $T$ where every node has at least one edge associated, and a weight function $w:S\to\mathbb R^+$ you want a subset $S_0\subset S$ of minimal total weight such that for every $t\in T,$ there is an edge $\{s,t\}$ with $s\in S_0.$ $\endgroup$ Oct 6, 2021 at 23:59
  • 1
    $\begingroup$ @ThomasAndrews Indeed, this is what I meant by "experimenting with different subsets". Thinking about it, this seems to be related to the hitting set problem. For each member of the list, find its set of prime factors, so we now have a collection of subsets of the prime factors. We are looking for "hitting sets", a subset of prime factors that contains at least one member from each subset in that collection. These are our candidates and we want the one with smallest product (not necessarily the one with fewest members, e.g. $2\times3$ beat $7$) $\endgroup$
    – Silverfish
    Oct 7, 2021 at 0:12
  • 3
    $\begingroup$ Consider the sets of prime divisors of your numbers: $\{2\},\{2,3\},\{3,5\},\{7\}$. I think you're looking for a minimal transversal of these sets, a smallest set that intersects each of the given sets (but with the extra arithmetic condition that "minimal" means smallest product). $\endgroup$ Oct 7, 2021 at 12:22
  • 3
    $\begingroup$ @GerryMyerson Interesting! Wikipedia defines a transversal in combinatorics as a "set containing exactly one element from each member of the collection" of sets. While in vertex covers in hypergraphs (like a graph but hyper-edges can join any number of vertices, not just 2: take primes as vertices & you've listed 4 hyper-edges), "transversal", "hitting set" & "vertex-cover" are treated as synonyms, a subset of vertices containing at least one vertex from each hyper-edge $\endgroup$
    – Silverfish
    Oct 7, 2021 at 12:48

4 Answers 4

5
+100
$\begingroup$

I think this should be NP-hard, even if the prime factorisation is given.

The idea here is that given an instance of the (NP-hard) set cover problem with $n$ sets $S_1,\ldots,S_n\subset U$, you can reduce it to this problem by choosing $n$ primes $p_1,\ldots,p_n$ between $2^n$ and $2^{n+1}$, and allocating one prime to each set. Now encode each element $x\in U$ by $f(x)=\prod_{i:x\in S_i}p_i$.

A minimal set cover corresponds to a minimal-cardinality set of primes whose product has a common factor with $f(x)$ for each $x$. Also, the bounds on the primes mean that the set with minimal product (which is what you need for your problem) must also be a minimal-cardinality set.

The difficulty here is finding a suitable set of primes in polynomial time. There is certainly an algorithm to do this in polynomial expected time - pick numbers in range at random and use a polynomial-time primality test. The prime number theorem implies there are enough primes in range that you find $n$ of them after an expected polynomial number (in $n$) of tries. Whether there is a deterministic algorithm to find such a set (even assuming, say, generalised Riemann hypothesis) I don't know.

$\endgroup$
5
  • $\begingroup$ To check my understanding: given universe $U=\{a,b,c,d\}$ and $S_1=\{a,b,c\}$, $S_2=\{a,b\}$, $S_3=\{a,c\}$, $S_4=\{b,c,d\}$ we can assign the four primes $2^4<17<19<23<29<2^5$ and encode $a=17\cdot 19\cdot 23$, $b=17\cdot 19\cdot 29$, $c=17\cdot 23\cdot 29$, $d=29$. For the set cover problem we need $S_4$ or else we miss $d$; now we only miss $a$ so any of $S_1,S_2,S_3$ will do, hence minimal cardinality is 2. For the problem of finding a number not coprime to any of $a,b,c,d$ we need a factor of 29 or we are coprime to $d$. We now only need one of $17,19,23$ to get a common factor with $a$. $\endgroup$
    – Silverfish
    Oct 16, 2021 at 21:11
  • $\begingroup$ So I can see finding a minimal-cardinality set of primes works exactly the same way as finding a minimal-cardinality set cover. I think the argument for the $2^n<p_i<2^{n+1}$ bounds is that the worst possible cardinality-$k$ product would use $k$ primes just below $2^{n+1}$; it cannot be improved by using $k+1$ or more primes even if they're only just above $2^n$, since product of $k+1$ small primes $>(2^n)^{k+1}=2^{nk+n}>(2^{n+1})^k=2^{nk+k}>$ product of $k$ large primes. Hence the minimal product must comes from one of the sets of primes of minimal cardinality $\endgroup$
    – Silverfish
    Oct 16, 2021 at 21:28
  • $\begingroup$ Clearly if the least common non-coprime problem could be solved in polynomial time (given the prime factorisation), and if primes could be found in polynomial time such that any set cover problem could be encoded as a least common non-coprime problem, then set cover problems could be solved in polynomial time (which we know is false). Where it gets fuzzier for me is: what happens if we can't find a polynomial-time algorithm for finding those primes for the encoding - let's say if it can only be done in polynomial expected time, how does this affect the result? $\endgroup$
    – Silverfish
    Oct 16, 2021 at 23:06
  • $\begingroup$ This does show that every set cover problem can be restated as a least common non-coprime problem, and so there are infinitely many least common non-coprime problems which will be nasty. But I wonder what can be said about the (also infinitely many) lowest common non-coprime problems which aren't equivalent to a minimal-cardinality set cover problem, eg for $\{14,21\}$ where $2\times 3<7$ despite $\{2,3\}$ having greater cardinality than $\{7\}$. Really interesting answer!! $\endgroup$
    – Silverfish
    Oct 16, 2021 at 23:20
  • $\begingroup$ Have awarded the +100 bounty as this seems the most convincing answer to date - clear the greedy algorithms are suboptimal, and there seem to be counterexamples to this being solved by linear programming (as opposed to integer linear programming). Haven't accepted this answer as I think there are still some details to polish out - may run another bounty later to draw more attention to this surprisingly tricky problem! $\endgroup$
    – Silverfish
    Oct 18, 2021 at 13:19
5
$\begingroup$

[Edited]This problem is an integer linear programming problem. Let the prime factors be ${ p_i | i=1\ldots n }$, and the radicals of the input numbers be $Rad(n_k) = \prod_{i\in S_k} p_i$. The problem is then finding \begin{equation} \min \sum_i x_i \log p_i \end{equation} given the constraints $x_i \in {0,1}$ and $\sum_{i\in S_k} x_i \geq 1$.

$\endgroup$
17
  • 2
    $\begingroup$ Would be nice to see a proof of correctness as a few bits confuse me. Take $\{6,10,15\}$, so $p_i=2,3,5$ and any pair of primes "works" but the solution to the (log of) minimum product problem $x_1\log2+x_2\log3+x_3\log5$ is $(1,1,0)$ since $\log 2+\log 3<\log2+\log 5<\log3+\log5$. Whereas just trying to solve the hitting set problem (smallest number of primes) by minimising $x_1+x_2+x_3$ fails with LP, giving $(.5,.5,.5)$. Any of $(1,1,0)$, $(1,0,1)$, $(0,1,1)$ solves the ILP problem. However, it doesn't seem true in this case that "some subset (size $\ge2$) of $p_i$ occurs in multiple $n$"? $\endgroup$
    – Silverfish
    Oct 15, 2021 at 14:07
  • 1
    $\begingroup$ It would be useful to define $S_k$ in this answer. I had to guess. You don’t need to define the radical, just say $S_k$ is the set of prime divisors of $n_k.$ $\endgroup$ Oct 15, 2021 at 19:12
  • 1
    $\begingroup$ @greg.Martin While it is true this is an integer linear programming problem, this answerer insists straight linear programming is enough. This is a bone of contention, so it seems to be unwise to edit the meaning of the answer. $\endgroup$ Oct 15, 2021 at 21:40
  • 2
    $\begingroup$ You still haven’t said why the example of $6,10,15$ yielding minimum when $x_i=1/2,$ and value $\frac12\log(30)<\log(6)$ can give you an integer answer, @Craig $\endgroup$ Oct 16, 2021 at 2:14
  • 1
    $\begingroup$ A more general example is if $p_1<p_2<\cdots <p_n$ and the numbers are the $\binom nm$ products of $m$ distinct primes, the integer minimum is $v_1=\sum_{k=1}^{n-m+1}\log p_k$ but there is a usually much smaller value $v_2=\frac1m\sum_{k=1}^n\log p_i.$ For example $m=3, p_*=(2,3,5,7,11,13,17,19),$ $v_1-v_2\approx 4.95.$ So non-integer solutions greatly lower the upper bound. $\endgroup$ Oct 16, 2021 at 20:02
3
$\begingroup$

This is a wrong answer, but a better greedy algorithm than the greedy algorithms provided so far.

If $P$ is your set of primes, and $N_1,\dots,N_k$ are the sets of prime factors for each number, then define, for $p\in P$: $$m_p=|\{i\mid p\in N_i\}|$$ Then find $p_0\in P$ which minimizes $v_p=\frac{\log p}{m_p}.$

Then remove the numbers divisible by $p_0,$ and start again.

So, for example, $\{3\cdot 7,5\cdot 7,2\}$ we get $m_2=1,m_3=1,m_5=1,m_7=2.$ $p_0=7$ minimizes, and we are left with the set $\{2\}.$ We get the answer $14.$

Essentially, $v_p=\frac {\log p}{m_p}$ is the “price per unit” of choosing $p$ as the first factor.

This kind of greedy algorithm usually doesn’t work in all cases, but at least it does better than giving the wrong “value,” minimizing $\log p$ (or equivalently, just minimizing $p.$) Minimizing $\log p$ is like minimizing the cost without looking at how many units it buys.


A simple example where my algorithm doesn’t work is $\{2\cdot 7,5\cdot 7\},$ which gives $10$ when $7$ is the answer.

Another example where my algorithm doesn’t work:

$$\{3,5\}\cup \left(3\cdot 7\cdot\{p_1,\dots,p_n\}\right)\cup \left(5\cdot 7\cdot\{p_1,\dots,p_n\}\right)$$ where the $p_i>7$ are distinct primes.

$m_7=2n, m_3=m_5=n+1,$ and for large enough $n,$ $$\frac{\log 7}{2n}<\frac{\log 3}{n+1}.$$ $n\geq 8$ is enough to fail.


The key reason the greedy algorithm doesn’t work is that at the next step, the value of the primes changes.

Also, when the $N_i$ are small, we have fewer options to choose from. It might be better to find a minimum-sized $N_i,$ and find the prime in that $N_i$ which minimizes the cost. In particular, then, when some $N_i$ are singletons, we get those elements immediately, as in my complicated counterexample.

But it still doesn’t solve the case $\{2\cdot7,5\cdot7\}.$

If $p_1<p_2<p_3,$ my algorithm gives the wrong answer for $\{p_1p_3,p_2p_3\}$ when $p_1^2<p_3<p_1p_2.$ The “smallest primes” greedy algorithm gives the wrong answer whenever $p_1p_2>p_3.$ So there is a slight improvement in this case.


Maybe slightly better: For $i=1,\dots,k$ let $p_i\in N_i$ minimize $v_{p_i}$ in $N_i.$ Let $s_i$ be the second best $v_{q_i}$ in $N_i,$ or $+\infty$ if $N_i$ has only one element. Then pick the $p_i$ which maximizes $s_{i}-v_{p_i}.$

That is, pick an element from a set where the cost increase goes up the most if we don't select $p.$

Then $\{p_1\cdot p_3,p_2\cdot p_3\}$ gives $p_3$ first if $\log p_2-\log(p_3)/2 >\log(p_3)/2-\log p_1$ or if $p_1p_2>p_3.$


This algorithm fails with $$\{2\cdot 31,3\cdot 31,5\cdot 31\},$$ since $\log(31)/3-\log(2)<\log(5)-\log(31)/3,$ so my greedy algorithm chooses $31$ first.

$\endgroup$
2
  • $\begingroup$ Interesting to see a "wrong" approach so (+1) for thinking through what does and doesn't work. I went through a similar thought process about the "cost" of picking a prime, which is exactly how I constructed some "nasty" examples, some of which I specifically included in my question for this purpose. Indeed it was the nastier examples that persuaded me this looked like it would take more than a simple alteration to the standard LCM algorithm, and hence worth asking the question in the first place $\endgroup$
    – Silverfish
    Oct 15, 2021 at 22:32
  • $\begingroup$ Yeah, I mostly posted because the other greedy algorithms are so obviously wrong, and I wanted to indicate what was wrong about them - the wrong valuation of the primes. But tweaking a greedy algorithm doesn't remove all the problems with greedy algorithms. $\endgroup$ Oct 15, 2021 at 23:25
1
$\begingroup$

I think that a modified Sieve of Eratosthenes works, if you assume that you already know what the prime numbers are. Instead of applying it to the natural numbers, apply it to the set of integers under analysis.

If any of the numbers in the set have $2$ as a factor, record $2$ in a save list and remove all members of the set that are $\equiv 0 \bmod 2$.

If any of the remaining numbers in the set have $3$ as a factor, note $3$ in the save list and remove all members of the set that are $\equiv 0 \bmod 3$.

Repeat for each successively larger prime. You will eventually remove every number in any finite set, and you will have a finite list of saved primes.

Edits in response to comment by OP:

Multiply the members of the list to obtain a product.

Next determine the gcd of the set of numbers, and compare it with the product just obtained.

The smaller of the product and the gcd is at least a very good candidate for the smallest number not coprime to any member of the original set. If I can tighten this up further, I will add more.

$\endgroup$
7
  • $\begingroup$ What made me suspect that this is a bit harder than it looks is the example of $\{2 \times 5, 3 \times 5, 2 \times 5\ \times 19 \} \text{ versus } \{2 \times 7, 3 \times 7, 2 \times 7 \times 19 \}$. Your method gives 6 for both, if I understand you correctly, but 5 is a better answer for the first set (whereas 7 isn't for the second set). $\endgroup$
    – Silverfish
    Oct 13, 2021 at 16:17
  • $\begingroup$ Thanks for the edit. The role of the gcd is interesting! Often it will be 1, unless there is a prime factor all the listed numbers share. In this case the gcd is not coprime to any member of the set, and nor is its smallest prime factor which is an even better candidate. Nevertheless, $\{2 \times 7, 3 \times 7, 2 \times 7 \times 19 \}$ has gcd $7$ (itself the smallest prime factor they all share) but is still beaten by $2 \times 3 = 6$. Just establishing some bounds to the problem can still be useful though, if it reduces the subsets of primes to check (gcd=7 shows we don't need to try 19) $\endgroup$
    – Silverfish
    Oct 13, 2021 at 17:27
  • $\begingroup$ I'm hung up on considering a set in which most members have a common factor, but one or a few don't share that factor. The common factor shared by most won't appear in the gcd, but may impact the number you seek in your question in a way that I can't as yet systematize in my thinking. $\endgroup$ Oct 13, 2021 at 18:33
  • $\begingroup$ This gives $30$ for $\{2\cdot 7,3\cdot 7,5\cdot 7\}$ when $7$ will do. We are seeking the smallest product. $\endgroup$ Oct 15, 2021 at 19:20
  • $\begingroup$ @Thomas Andrews Using the method as modified in the edit which compares the product to the gcd actually gives $7$ in the example you give, not $30$ $\endgroup$ Oct 15, 2021 at 19:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .