# Representation as sum of unit fractions: primitive recursive?

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?

• It is worth mentioning that these are Egyptian fractions: en.wikipedia.org/wiki/Egyptian_fraction – Andrej Bauer Jan 2 '15 at 23:19
• 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 Jan 4 '15 at 6:04

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$.
• 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 supports Monica Jan 4 '15 at 19:38
• Sorry, NEXPEXP, if $m$ is given in binary. – Emil Jeřábek supports Monica Jan 4 '15 at 19:50