Modified version of $\log_2(x)$

Question

Show that the function $f(x) = \begin{cases}\log_2(x),&\text{ if $x$ is a power of $2$}\\ \text{undefined},&\text{ otherwise}\end{cases}$ is recursive but not primitive recursive.

I'm not sure how to show this. To show it is not primitive recursive, I think I need to show that it must be defined using minimization (not bounded); primitive recursive functions are the successor function, zero functions, projection functions, and any compositions of the above functions or functions $f$ such that there exist primitive recursive functions $g$ and $h$ so that $f(x, 0) = g(x)$ and $f(x,n+1) = h(x,n,f(n))$. I know how to show that the function $f(x) = \lfloor \log_2(x+1) \rfloor$ is primitive recursive. I think I need to define a recursive predicate to determine whether $x$ is a power of $2$ (including negative powers). That's easy because that's just repeated division and addition. However, I'm not sure how to show this is not primitive recursive.

Answer 1

This is a rather silly situation: the only reason $f$ is not primitive recursive is that $f$ is sometimes undefined. All primitive recursive functions are defined everywhere, basically by definition.

In particular, if we modify the definition of $f$ so that $f(x)=17$ (say) whenever $x$ is not a power of $2$, we do indeed get a primitive recursive function.

Answer 2

Clearly, $f(x)$ can be computed recursively by repeated multiplications or divisions, as you said. There is a computable bound to the number of multiplies or divisions, one can use $x$ for $x >= 1$ and $1/x$ for $x<1$. The upper bound does not need to be a close one to fit the requirement, it just has to be an upper bound. This implies that $f(x)$ is primitive recursive.