6
$\begingroup$

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)$?

$\endgroup$
1
3
$\begingroup$

In fact, this is listed as an open problem in the Wikipedia page on Egyptian Fractions, presumably because they do use the output size as a parameter.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ What about polynomial in the size of the output? $\endgroup$ – Igor Rivin Jan 2 '15 at 18:18
  • $\begingroup$ 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). $\endgroup$ – Jeremy Rouse Jan 2 '15 at 20:09

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.