How often can I divide a number until I hit a certain limit.

Question

I'm have an algorithm that can solve a certain problem in a specific number of steps.

Since this algorithm is recursive I'm unsure how to describe it mathematically.

Generally speaking the algorithm roughly follows the recession: a(n+1) = 3a(n)-1 and the closest equation I could find for this was y = 0.5*(3 + e^(1.09861*I)) (Using fitting with gnuplot).

Roughly simplified, the complexity of solving my problem for a specific value "I" depends on how often I can divide "I" by 3 ((I-1/3) to be exact) until I hit a number <= 5.

So I am searching for a mathematical way to express "Number of times I can divide "I" by 3.

The data below shows the exact complexities. (For an input of I = 6, the complexity is N^2, for I = 15, it's N^3, etc)

2   6
3   15
4   42
5   123
6   366
7   1095
8   3282
9   9843
10  29526

Answer 1

Hint: use the log. Answer: $\mathrm{ceil}(\frac{\log(I-1/3)-\log 5}{\log 3})$.

Answer 2

Notice that if

$$a3^d\le i<a3^{d+1},$$ $d$ is the number of times you can divide by $3$ until the integer quotient is $a$.

Hence

$$\log_3 a+d\le\log_3i<\log_3a+d+1$$

and

$$d=\lfloor\log_3i-\log_3a\rfloor.$$