Showing that the set of integers with an odd number of 2s in their factorizations is primitive recursive

Question

Knowing that: $p(i)$, the $i^{th}$ prime function, $\pi_i(m)$, the exponent of prime $p(i)$,and any other basic primitive recursive function hold, how could a primitive recursive relation be built for the above? Any hits would be great. Thank you

Answer 1

We already know $O$ to be the zero function, which is primitive recursive. Let $D$ be the relation that will output $0$ if $y$ is odd, and $1$ if $y$ is even. Note That $E(x,y)$ is also known to be primitive recursive. Let $\chi_D$ denote the characteristic function of the relation $D$. $\chi_D(0) = E(0,0) = 1$. $\chi_D(Sy) = E(0,\chi_D(y))$. If $y$ is odd, $\chi_D(y) = 0$ and thus $\chi_D(Sy) = E(0,0) = 1$. If $y$ is even, $\chi_D(y) = 1$ and thus $\chi_D(Sy) = 0 \rightarrow y+1$ is odd. So $D$ is primitive recursive.

Let $T$ be the set of integers with an odd number of twos in their prime factorization. Let $\chi_T(m)$ be the characteristic function which outputs 0 if $m \in T$, and $1$ otherwise. Let $\pi_1(m)$ denote the number of $2s$ in the prime factorization of $m$.

$\chi_T(0) = \chi_D(\pi_1(0)) = \chi_D(0) = 1.$ $\chi_T(Sy) = \chi_D(\pi_1(A(S0,y))).$ So $\chi_T$ is also primitive recursive, and $T$ is primitive recursive.