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

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.

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.

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]$$.