Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
great, thank you! I tried it out on paper and it works. I'm a bit ashamed, but could you please explain me how (why) your definition of F works? –  muffel Jul 15 '12 at 20:17
1  
Sure. Essentially, we know that $\log_{b}(n) = x$ if $b^x = n$. So, we do recursion by letting $b$ be a variable, and iterating $n$. Since $b$ is an integer greater than $0$, as $x$ increases, so does $b^x$. What we want to do is to keep on increasing $x$ until we hit $n$. Taking the floor function means we choose the largest $x$ for which $b^x$ is still less than or equal to $n$. At each step in the recursion, we increment $n$ by one. It is possible that by increasing $n$, we can fit another power of $b$ inside of it. In that case, we want to increment $x$ from the previous step...(cntd) –  Isaac Solomon Jul 15 '12 at 21:58
1  
It is also possible that even though we now considering $n+1$, $b^x$ is still the largest power of $b$ below $n+1$. In that case, we want to fix $x$ from the previous step. Here's a concrete example. Let $b = 3$, and suppose $n = 25$. Well, the log function will give me $x=2$, since $3^2 \leq 25 < 3^3$. Next, we increment to $n=26$, and we reconsider if $x=2$ is still the best choice. It is, as $3^2 \leq 26 < 3^3$. But now, increment again to $n=27$. In this case, $3^2 \leq 27 = 3^3$, so $x = 3$ isn't too large. In this scenario, we increment $x$ to $3$, and continue... –  Isaac Solomon Jul 15 '12 at 22:02
    
thank you so much! I finally got it –  muffel Jul 16 '12 at 14:48

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.