# Minimum number of unit fractions to sum up a given positive rational

For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$, see this article by Paul Erdös and Sherman Stein (Sums of distinct unit fractions. Proceedings of the American Mathematical Society, 14(1), 126-131, 1963.) . Let $m(p,q)$ denote the minimal cardinality of such a subset $S$. Is there a polynomial-time algorithm to determine $m(p,q)$?

No such polynomial-time algorithm exists because in some instances it would take too long to write down (or store in memory) the answer. In particular, if $n$ is a positive integer, then we have $\sum_{k=1}^{m(n,1)} \frac{1}{k} \geq n$, which implies that $m(n,1) \geq \frac{1}{5} e^{n}$. In such an instance, the number of input bits is about $\log_{2}(n)$ and the number of output bits is around $n$.
• The question is still quite subtle for fractions between 0 and 1. In this case, $m(p,q)$ is quite small ($O(\sqrt{\log(q)})$), but determining the precise value is probably quite hard (as hard as factoring in some cases probably). – Jeremy Rouse Jan 2 '15 at 20:09