How many times would I have to recursively apply the function ceil(1/3 x) for it to be >= x

Question

Suppose I have a function f(x)=ceiling(x/3) where x is a positive integer >1, how many times would I have to apply the function recursively before the result becomes 1? Is there a non-brute force way to calculate this?

Answer 1

If $x = 3n+k$ where $1 \le k \le 3$, then $f(x) =\lceil n+k/3 \rceil =n+1 $ so

$\begin{array}\\ x-f(x) &=3n+k -(n+1)\\ &=2n+k-1\\ &=2(x-k)/3+k-1\\ &=2x/3-2k/3+k-1\\ &=2x/3+k/3-1\\ &\ge 2x/3-2/3\\ &= 2(x-1)/3\\ \end{array} $

This is at least $x/2$ when $2(x-1)/3 \ge x/2 $ or $x/6 \ge 2/3 $ or $x \ge 4$.

Therefore, for $x \ge 4$, $f(x) \le x/2$, so that the number of iterations to reach 4 is $O(\log x)$.

Once there, $f(4) = \lceil 4/3 \rceil =2$, $f(3) = \lceil 3/3 \rceil =1$, $f(2) = \lceil 2/3 \rceil =1$, and $f(1) = \lceil 1/3 \rceil =1$.

This is at most two iterations more, which does not affect the $O(\log x)$ result.

For a lower bound, $f(x) \ge x/3$, so at least $\log_3 x$ steps are needed.

Therefore $\Theta(\log x)$ steps are needed.

Answer 2

Hint: show that if $3^k < n \le 3^{k+1}$, then $3^{k-1} < f(n) \le 3^k$.