0
$\begingroup$

Subset Product- Given $N$ and a list of positive divisors $S$, decide if there is a product combination equal to $N$

  • We will sort $S$ in numerical order from smallest to largest in order to find out the maximum combination size to avoid redundancy.
  • We will remove non-divisors in $S$. This does not impact the correctness, as no possible combination could yield N if there's a non-divisor in that combination.

Iterate over divisors of $N$ in $S$ and calculate the maximum combination size. We multiply each divisor in $S$ until the product $<=$ $N$

Isn't the sum of the prime exponents the bound for this?

$O(2^{\text{$Max-combination-size$}})$

We only allow one duplicate of 1 in S (any product combination of 1 is always 1) , to prevent redundant combinations and we sort S from smallest to largest which is a requirement to get $Max-combination-size$. $Max-combination-size$ basically ensures we don't do redundant combinations that will always yield a product > $N$. So the algorithm runs in $ O(N^M)$ is substantially smaller in magnitude compared to N.

So, we got an efficient algorithm in the value of N??

So there is a pseudo-polynomial algorithm, I just wanted to know if this is always the case if we look at number theorems when it comes to divisors and the value of N?

$\endgroup$
8
  • $\begingroup$ The number of divisors of $n$, $d(n)$ isn't $\mathcal{O}(\log n)$. If I remember correctly, it's $\Theta(e^{\frac{\log n}{\log \log n}})$. Anyways, the subset-product problem has a very obvious pseudo-polynomial algorithm via dynamic programming (the algorithm is essentially the same as the simple dynamic programming solution to the subset-sum problem). I'm not sure what you are asking in your last sentence. $\endgroup$ Commented Mar 17, 2024 at 10:07
  • $\begingroup$ @SharpEdged At worse, I thought it was sqrt(N), but I realized the sum of the exponents of primes could be what M is doing for the maximum combination size. I think that's logarithmic at least on average. $\endgroup$ Commented Mar 17, 2024 at 10:58
  • $\begingroup$ Is there an infinite number of positive integers for which the sum of the prime exponents in their prime factorization significantly exceeds the logarithm of N?? Looking for those non-trivial inputs would be very important for my research hobby. $\endgroup$ Commented Mar 17, 2024 at 12:58
  • $\begingroup$ Do powers of primes only have n divisors for $prime^n$? If so, that's a trivial input. Just get total product of S. Edit: Or n+1?? $\endgroup$ Commented Mar 17, 2024 at 13:14
  • 1
    $\begingroup$ There is a simple modification which will make the dynamic programming approach use $\mathcal{O}(d(n))$ memory - which should be comparable to the memory usage of your algorithm. This modification will also make the running time $\mathcal{O}((d(n))^2)$, which is quite interesting as it's faster than pseudo-polynomial time. I'm honestly not sure how to prove that your algorithm is pseudo-polynomial, I might try again later. $\endgroup$ Commented Mar 18, 2024 at 7:55

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.