0
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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