Skip to main content
added 12 characters in body
Source Link

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

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 a finite subset $S\subseteq U$ such that $\frac{m}{n} = \sum_{u\in S} u$?

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

Source Link

Positive rational numbers as sum of unit fractions

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 a finite subset $S\subseteq U$ such that $\frac{m}{n} = \sum_{u\in S} u$?