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)$?
$\begingroup$
$\endgroup$
1
asked Jan 2, 2015 at 14:41
-
$\begingroup$ Distantly related: mathoverflow.net/questions/33628/… $\endgroup$– Gerry MyersonJan 2, 2015 at 14:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Jan 2, 2015 at 18:29
$\begingroup$
$\endgroup$
2
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$.
answered Jan 2, 2015 at 16:55
-
$\begingroup$ What about polynomial in the size of the output? $\endgroup$ Jan 2, 2015 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$ Jan 2, 2015 at 20:09