# Counting Steps for Iterated Function with Ceiling Terms

If I have the following iterated function: $$L_{i+1} = \left\lceil \frac{N}{\left\lceil \frac{N}{L_{i}} \right\rceil-1} \right\rceil, L_{0} = 1$$

I am trying to find $$k$$ such that $$L_{k} = N$$. Is there a way to derive a closed form expression for $$k$$ as a function of $$N$$ or an upper limit on $$k$$ which is tighter than $$N$$?

I tried to get an estimate of how $$k$$ increases as $$N$$ grows exponentially from $$10^1 .. 10^q$$ and it seems to have an order of $$C(q)^{\log{q}}$$ with $$C(q)$$ decreasing in $$q$$, but I could not find a way to prove it by using the ceiling inequality $$\lceil x \rceil = y \rightarrow y-1 < x \leq y$$. I am not very knowledgable with discrete maths, so I am asking if you have some ideas that can help with this nested ceiling expression.

Edit: We know now that $$k = \lceil 2\sqrt{N} - 1 \rceil$$, so the question is how to get there from the iterated function?

$$k$$ will be close to $$2\sqrt N$$. When $$L_i$$ is less than $$\sqrt N$$, we have $$L_{i+1}=L_i+1$$. When $$L_i$$ is well greater than $$\sqrt N, \frac N{L_i}$$ decreases by $$1$$ each time. Each part takes about $$\sqrt N$$ steps. The ceilings make it hard to do a solid analysis.
• Thank you. I just got to a similar conclusion. More precisely $\lceil 2\sqrt{N} - 1 \rceil$. – Muhammad R. Soliman May 2 '19 at 0:11
• Could you please explain why $L_{i+1} = L_i +1$ when $L_{i} < \sqrt{N}$? – Muhammad R. Soliman May 2 '19 at 12:41
• I can't find an easy proof. You need two pieces-one to show that $L_i$ is strictly increasing and one to show it doesn't increase by more than $1$. The second half comes because the fraction doesn't change much for a change of $1$ in the denominator. The first from the fact that $\lceil \frac N{L_i} \rceil-1$ is strictly less than $\frac N{L_i}$ but you have to show the outer divisions can't round up to the same thing. That is where I am stuck. – Ross Millikan May 2 '19 at 15:04