RAM program, which compute $ \lfloor \log_3(n) \rfloor $.

Question

Actually I need $\lceil \log_2(n) \rceil $ and $ \lfloor \log_3(n) \rfloor$.

but $\lceil \log_2(n) \rceil $ was no problem. I will now explain what I have done regarding $\lceil \log_2(n) \rceil $, so you can see that your answer for $ \lfloor \log_3(n) \rfloor$ doesn't have to be a complete program. I just need the idea.

n = 3 #(starting value)

r = 0 #answer

while n > 1:

    n = n/2 + ( n mod 2 )

    r += 1

print(r)

for example $n = 3$. first we would get $\frac{3}{2} + ( 3 \mod 2 ) = 2$. we increment and get $r=1$. then $\frac{2}{2} + ( 2 \mod 2 ) = 1$. and we get $r=2$. end of the algorithm. this is $\lceil \log_2(3) \rceil = 2 $.

but what can I do for $ \lfloor \log_3(n) \rfloor$?

Maybe $\frac{n}{3} + ( n \mod 3 ) \leq 2$ for every loop? Am I too naive?

Answer 1

By definition of the floor function,

$$\log_3n-1<l=\lfloor\log_3n\rfloor\le\log_3n$$

implies

$$\frac n3<3^l\le n$$

and $l$ is the largest power of $3$ that does not exceed $n$.

l, p= 0, 3
while p <= n:
    l, p= l+1, 3*p