Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following problem (phrased with the use of a black box).

You choose $n$ numbers $X = \{x_1,\ldots,x_n\}$ and pass it to a black box that returns a list $Y = \{y_1,\ldots,y_m\}$ where each of the elements is a product of the elements of some $k-subset$ of $X$. That is for every $1 \leq i \leq m$ the black box picks an element $ Y_i \in {X \choose k}$ and sets $$y_i = \prod_{p \in Y_i} p.$$

Given that I am able to choose the elements of $X$ I am wondering how should I pick them in order to be able to compute the number of intersecting $(Y_i,Y_j)$ pairs as efficiently as possible.

One thing is take $X$ to contain only pairwise coprime elements and then check the if the pairs $(y_i,y_j)$ are coprime or not.

I am wondering, if there is something even more slicker that can be done that would then allow to compute the number of intersecting pairs in say $O(m)$ or at least faster than $O(m^2)$?

share|cite|improve this question
up vote 1 down vote accepted

I'm not sure if this answers your question, but you could try making each $x_i=2^{2^{i-1}}$. That is, $X=\{2,4,16,256,\ldots\}$ , and each element is the square of the previous one. Now, each of the $y_i$ will be a power of 2, where the binary representation of the exponent will indicate which of the $x_i$ comprise the product. I'm not sure what order the computation would be to evaluate this, but I imagine that it would be better than prime factorisation.

share|cite|improve this answer
Thats a neat answer - thanks! However I am afraid that the magnitude of the elements in $X$ would bloat out the complexity of the algorithm :( – Jernej Aug 11 '12 at 9:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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