3
$\begingroup$

Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$.

Problem

Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (not pseudo-polynomial) time for every $\alpha \in \mathbb{N}$ and $P, p_1, ... , p_n$ unknown.

First attempts

$P$ and $ p_1, ... p_n$ can be calculated with $P = \sqrt[n-1]{\prod_{i=1}^{n}{a_i}}$ and $p_i = P / a_i$.

Now we can write the problem as $\alpha/P = 1/p_{i_1} + ... + 1/p_{i_n}$

$\endgroup$
3
$\begingroup$

The observation is that the denominator of the reduced fraction $1/p_{i_1} + \cdots + 1/p_{i_m}$ is $p_{i_1} \cdots p_{i_m}$. To see this, it suffices to notice that the (unreduced) numerator isn't divisible by any $p_{i_j}$. Indeed, the numerator is simply $$ \frac{p_{i_1} \cdots p_{i_m}}{p_{i_1}} + \cdots + \frac{p_{i_1} \cdots p_{i_m}}{p_{i_m}}. $$ All terms but the $j$th are products of $p_{i_j}$, but the $j$th term isn't, so the numerator isn't divisible by $p_{i_j}$.

As a consequence, if $\alpha/P$ is a sum of reciprocals of distinct primes, then we can read off the primes from the prime factorization of the reduced form of $\alpha/P$. We can compute this reduced form efficiently using GCD. Since we know $p_1,\ldots,p_n$, we can figure out whether the denominator is a product of a subset of $\{p_1,\ldots,p_n\}$, and if so, it only remains to check whether $\alpha/P$ is equal to the sum of reciprocals of prime in this subset.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As a consequence, can we say, that every $p_j$, that is not part of the subset, is a prime factor of $\alpha$? $\endgroup$ – SmashTheStack Oct 24 '19 at 21:52
  • $\begingroup$ This sounds plausible. Perhaps you can prove it? $\endgroup$ – Yuval Filmus Oct 24 '19 at 22:22
  • $\begingroup$ Yes it is, it can be derived from your answer. Thank you! $\endgroup$ – SmashTheStack Oct 24 '19 at 22:23

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.