1
$\begingroup$

Let $U = \{\frac{1}{n}: n\in\mathbb{N}, n>0\}$ be the set of unit fractions. For integers $m,n>0$ there is always a finite subset $S\subseteq U$ such that $\frac{m}{n} = \sum_{u\in S} u$, see this article by Paul Erdös and Sherman Stein.

Is there a polynomial-time algorithm that takes two positive integers $m,n$ as input and gives the minimum number of elements of a finite subset $S\subseteq U$ such that $\frac{m}{n} = \sum_{u\in S} u$?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

This is the Egyptian fractions problem, and there are a number of algorithms. Wikipedia claims the computational complexity is unknown.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .