Show that $f(x,y)=\lfloor x/y \rfloor$ is primitive recursive

Question

So, I want to show that the aforementioned function is primitive recursive.

Here's my idea: let $k$ be the smallest number such that $ky > x$. Clearly then $f(x,y) = k -1$.

I then have the following procedure for computing $f$ in mind

for k = 0:x
    if ky > x
        break
    end
end
if y < x
    f = k-1
else f = 0
end

Though I'm having a hard time expressing this in the 'language' of primitive recursive functions.

More details: I guess I could define $f$ using bounded search / minimisation, i.e. $f(x,y) = (\mu k < (x+1))P(y,k,x) - 1$ where $P=\{ \langle y,k,x \rangle : yk > x \}$, but I would like to define the function using composition and primitive recursion.

---

Here are two solutions:

The first follows the hint from Rob and is very simple. We simply use primitive recursion with $f(0,y)$ as the base case.

\begin{equation} f(0,y)=0 \end{equation} \begin{equation} f(x+1,y) =\left\{ \begin{array}{rl} f(x,y) & \text{if } y \cdot (f(x,y)+1) > x,\\ f(x,y)+1& \text{otherwise.}\\ \end{array} \right. \end{equation}

The second is messier and goes like this: again let $k$ be the smallest number such that $ky>x$. We know that $f(x,y) = k-1$. So first we define the ternary function $g$:

\begin{equation} g(x,y,0) = 0 \end{equation} \begin{equation} g(x,y,z+1)=\left\{ \begin{array}{rl} g(x,y,z) & \text{if } y \cdot g(x,y,z) > x,\\ z & \text{if } y \cdot z > x,\\ z + 1 & \text{otherwise.} \end{array} \right. \end{equation}

And then we define the function $h(x,y) = g(x,y,x+2)$. So $h$ looks for the smallest number strictly less than $x+2$ that multiplied by $y$ yields a number greater than $x$ - the $k$ we are looking for. If $y=0$ then there is no such number and $h$ returns $x+2$.

Then \begin{equation} f(x,y) = \left\{ \begin{array}{rl} h(x,y) - 1 & \text{if } x > 0,\\ \text{undefined, if } x = 0. \end{array} \right. \end{equation}

Answer 1

Hints:

If $y = 0$, the problem is ill-defined and you can return some dummy value.

If $y \ge 1$, the base case of the recursive definition is $\lfloor 0/y \rfloor = 0$, and you need to work out how to define $\lfloor (x+1)/y\rfloor$ given $\lfloor x/y \rfloor$ and known primitive recursive functions of $x$ and $y$. To see how to do this think about the following questions:

• When is $\lfloor (x+1)/y \rfloor \neq \lfloor x/y \rfloor$?
• If $\lfloor (x+1)/y \rfloor \neq \lfloor x/y \rfloor$, what is $\lfloor (x+1)/y \rfloor - \lfloor x/y \rfloor$?