Why is $\log(b,n) = \lfloor \log_b(n) \rfloor$ primitive recursive?

Question

I read in an introduction to primitive recursive function and Wikipedia that $$\log(b,n) = \lfloor \log_b(n) \rfloor$$ is primitive recursive. But how can that be? Is there any easy proof (and therefore a definition of the function using only constants, projection, composition and primitive recursion)?

Thanks in advance!

Answer 1

I'll try and sketch a construction. Firstly, note that a function defined by primitive recursive cases from primitive recursive functions is still primitive recursive (rather easy to prove).

So, we attempt to define this by recursion on $n$. Since $\log_b(0)$ is not something we want to consider, we'll assume $b,n > 0$. Let

$$\log(b,1) = 0$$

Which is certainly primitive recursive. Then define

$$\log(b,n+1) = F(\log(b,n),b,n)$$

Where $F$ is the following function, defined by cases. $F$ takes $\log(b,n)+1$, and checks if

$$b^{(\log(b,n) + 1)} > n+1$$

In other words, it sees if $\log(b,n) + 1$ is still shooting too high. If it is, then we stick with what we've got: $\log(b,n)$. Otherwise, the time has finally come to move on up to $\log(b,n) + 1$, and so $F$ outputs that.

It's not hard to see that $F$ is defined by primitive recursive cases from primitive recursive functions, and so have shown that $\log(b,n)$ is primitive recursive.

Answer 2

It's primitive recursive because you can give an algorithm for computing it that uses only bounded loops: Find the largest integer $x$ such that $b^x \le n$. The loop need never execute more than $n$ times, hence it is bounded. (We are assuming $b>1$, since the logarithm is not defined otherwise.)

This can be translated into a combination of functions you describe, with the loop corresponding to primitive recursion, though it can be quite messy. Usually, when checking if something is primitive recursive, it's easier to think in terms of bounded loop algorithms.