Solving recurrence relation $f(n) = f(\lfloor\sqrt n\rfloor) + 1; f(1) = 1, f(2) = 1$

Question

As the title shows, I need help approaching a solution for recurrence relation:

$f(n) = f(\lfloor\sqrt n\rfloor) + 1$ if $n\ge3$

with initial values $f(1) = 1$, $f(2) = 1$

I am particularly confused by the square root. All I'm trying to get is $f(n)$ in just terms of $n$ without the recursion.

Answer 1

For every positive $n$ there is exactly one nonnegative integer $a$ with $$a^2\le n<(a+1)^2$$

We have $\lfloor \sqrt{n} \rfloor=a$. Hence, the function $f$ is constant between squares, then resets to a new value. That is, $$f(2)=f(3)=2$$ $$f(4)=f(5)=\cdots=f(8)=f(2)+1=3$$ $$f(9)=f(10)=\cdots=f(15)=f(3)+1=3$$ $$f(16)=f(17)=\cdots=f(24)=f(4)+1=4$$

Answer 2

For all $n > 2$ $$ f(n) = \left\lfloor \log_2 \left( \lfloor \log_3 (n) \rfloor \right) \right\rfloor $$ The previous answer mistakenly took $f(2) = 2$ rather than $1$.