# 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.
• As a consequence, can we say, that every $p_j$, that is not part of the subset, is a prime factor of $\alpha$? – SmashTheStack Oct 24 '19 at 21:52