Solve SUBSET SUM for Reciprocals of Primes 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}$
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.