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&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$.


Is $R$ primitive recursive, recursive, or recursively enumerable?
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$.

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