0
$\begingroup$

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)$?

1 Answers 1

1

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.

  • 0
    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 :(2012-08-11