# Primitive recursive identification of the digits into a binary expression.

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.

• By $i$-th digit do you mean the i-th digit where the first digit is the least significant digit? I.e. the i-th digit from the right when we write it as a binary number? Also, can you already assume some basic functions to be primitive recursive, such as multiplication or any constant functions? – Bram28 May 29 '17 at 0:07
• Yes, that's right. We consider that digit you spell and the functions you seem to need. – gibarian May 29 '17 at 0:11
• Did you already show multiplication to be primitive recursive? And any constant functions? – Bram28 May 29 '17 at 0:12

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