Primitive recursive identification of the digits into a binary expression.

Question

I would like to know which is the form of the primitive recursive function that gives the i-th digit of the binary expression of a given number.

Answer 1

OK, I assume you have already shown the quotient (quo) and remainder (rem) functions to be primtive recursive. Then what you want can be done as follows:

$binarydigit(n,i)=helpbinarydigit(n,i-1)$

$helpbinarydigit(n,0)= rem(n,2)$

$helpbinarydigit(n,i+1)=\begin{cases} helpbinarydigit(quo(n,2),i) & \text{if } rem(n,2)=0\\ helpbinarydigit(quo(n-1,2),i) & \text{if } rem(n,2)=1 \end{cases}$

Explanation:

You keep dividing $n$ by $2$, until you get to the right digit. As you divide by $2$, if the remainder is $1$, the first subtract $1$ before dividing by $2$. As such, you will in effect keep removing the least significant digit from the number in binary representation, until you get to the digit you want.