Representation as sum of unit fractions: primitive recursive?
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$.