<p>Consider $(p,q,m)\in R_k$ iff there is a set $S\subseteq \{\frac{1}{n}:n\in\mathbb{N}, n&gt; k\}$ such that $|S|=m$ and $\frac{p}{q}=\sum_{s\in S} s$, so $R=R_0$.</p>

<p>It is easy to see that $(p,q,m)\in R_k$ iff there is an $k&lt;\ell\le \frac {qm}p$ such that $(p\ell-q,q\ell,m-1)\in R_\ell$.</p>

CC BY-SA 3.0
2015-01-04T19:38:56.393Z
I suppose it should be $l\le qm/p$. If I understand the argument correctly, it also shows that if there is such a set $S$, there is one with $S\subseteq\{n^{-1}:n<(qm)^{2^m}\}$ or so, hence the problem is in NEXP.
Emil Jeřábek
CC BY-SA 3.0
2015-01-04T19:50:40.873Z
Sorry, NEXPEXP, if $m$ is given in binary.
Emil Jeřábek
CC BY-SA 3.0
2015-01-03T22:43:54.660Z
2015-01-04T20:42:05.633Z
2015-01-04T20:42:05.633Z
domotorp
<p>Consider the following ternary relation $R\subseteq\mathbb{N}^3$:</p>

<blockquote>
  <p>$(p,q,m)\in R$ iff $p,q&gt;0$ and there is a set $S\subseteq \{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $|S|=m$ and $\frac{p}{q}=\sum_{s\in S} s$.</p>
</blockquote>

<p>Is $R$ primitive recursive, recursive, or recursively enumerable?</p>

CC BY-SA 3.0
2015-01-02T23:19:08.323Z
It is worth mentioning that these are Egyptian fractions: http://en.wikipedia.org/wiki/Egyptian_fraction
Andrej Bauer
CC BY-SA 3.0
2015-01-04T06:04:47.700Z
The following paragraph from that article is I think directly relevant to this question: "It is possible to use brute-force search algorithms to find the Egyptian fraction representation of a given number with the fewest possible terms (Stewart 1992) or minimizing the largest denominator; however, such algorithms can be quite inefficient. The existence of polynomial time algorithms for these problems, or more generally the computational complexity of such problems, remains unknown."
David Eppstein
<computability>
Representation as sum of unit fractions: primitive recursive?
Dominic van der Zypen
# Representation as sum of unit fractions: primitive recursive?

(Asked by: username_0 on 2015-01-02)

Consider the following ternary relation $R\subseteq\mathbb{N}^3$:

> $(p,q,m)\in R$ iff $p,q>0$ and there is a set $S\subseteq \{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $|S|=m$ and $\frac{p}{q}=\sum\_{s\in S} s$.

Is $R$ primitive recursive, recursive, or recursively enumerable?

**Tags:** computability
> **Comments:**
> **username_1**: It is worth mentioning that these are Egyptian fractions: http://en.wikipedia.org/wiki/Egyptian_fraction  
> **username_2**: The following paragraph from that article is I think directly relevant to this question: "It is possible to use brute-force search algorithms to find the Egyptian fraction representation of a given number with the fewest possible terms (Stewart 1992) or minimizing the largest denominator; however, such algorithms can be quite inefficient. The existence of polynomial time algorithms for these problems, or more generally the computational complexity of such problems, remains unknown."  

---

## 1 answers

### Answer by username_3 on 2015-01-03. Score: 3

Consider $(p,q,m)\in R\_k$ iff there is a set $S\subseteq \{\frac{1}{n}:n\in\mathbb{N}, n> k\}$ such that $|S|=m$ and $\frac{p}{q}=\sum\_{s\in S} s$, so $R=R\_0$.

It is easy to see that $(p,q,m)\in R\_k$ iff there is an $k<\ell\le \frac {qm}p$ such that $(p\ell-q,q\ell,m-1)\in R\_\ell$.

> **Comments:**
> **username_4**: I suppose it should be $l\le qm/p$. If I understand the argument correctly, it also shows that if there is such a set $S$, there is one with $S\subseteq\{n^{-1}:n<(qm)^{2^m}\}$ or so, hence the problem is in NEXP.  
> **username_4**: Sorry, NEXPEXP, if $m$ is given in binary.  

---

