Find which k numbers from the given set of integers multiply to give us m

Question

Suppose we are given n integers and we are required to answer which k numbers from this set multiply to give us some defined number m. We are safe to assume that the answer exists. What are possible approaches to this problem? I mean some clever ideas or remarks that would suggest a good algorithm. There are no particular constraints, I am just curious about whether there is something about this problem that can reduce it to a more convenient form. Or else, how to prove that there is no solution other than doing a complete search, given that we only have constant amount of space.

Answer 1

If $i$ is one of the $n$ numbers $1,2,\ldots, n$ and $d$ is one of the $\tau(m)$ divisors of $m$, and $0\le j\le i$, let $f(i,j,d)$ denote the number of ways to write $d$ as product of exactly $j$ of the integrs $a_1,\ldots, a_i$. Then we are interested in $f(n,k,m)$ and have the recursion $$ f(i,j,d)=\begin{cases}1,&j=0, d=1\\0,&j=0,d\ne1\\0,&j>i\\0,&d\notin \Bbb Z\\f(i-1,j,d)+f(i-1,j-1,\frac d{a_i})&\text{otherwise}\end{cases}$$ Computationally, this may well be tractable with Dynamic Programming, provided the numbers $n,m,k$ are of manageable size.

Answer 2

So we want $x_1\cdot ..... x_k = M$.

First prime factorize everything: so that $x_i = p_{a_{i,1}}^{b_{i,1}}\cdot p_{a_{i,2}}^{b_{i,2}}\cdot....$ and $M = p_{m,1}^{c_{m,1}}\cdot p_{m,2}^{c_{m,2}}...$

We can only pick the $x_i$ that only have primes in common with $M$ and only to powers less, and then we must have the powers add up.

So if we have all numbers from $1$ to $100$ and we can choose $3$ of them and we want them to multiple to $1960$.

$1960 = 2^3*5*7^2$. So we can only chose from those whose primes are $2,5,7$ and only if all the powers of $2$ add to $3$ and only one power of $5$ and two powers of $7$.

So we can distribute the powers of $2$ as $[2*a, 2*b, 2*c]$ or $[4*a, 2*b, c]$ or $[8a, b, c]$.

The have only one power of $5$ so we can have $[10*a', 2b, 2c]$ or $[20*a', 2b,c]$ or $[4a, 10b', c]$ or $[4a, 2b, 5c']$ or $[40a', b, c]$ or $[8a, 5b', c]$.

And the two powers of $7$ can be clumped together as $49d$ given us: $[10,98, 2]$ or $[20,98,1]$ or $[20,2,49]$ or $[4,10,49]$ or $[4, 98,5]$ or $[40,49,1]$ or $[8,5,49]$.

Or they can spread giving us: $[70,14,2]$ or $[10,14,14]$ or $[20,14,7]$ or $[28,70,1]$ or $[28,10,7]$ or $[4,70,7]$ or $[28,14,5]$ or $[28,2,35]$ or $[4,14,35]$ or $[40,7,7]$ or $[56,35,1]$ or $[56,5,7]$ or $[8,35,7]$.