0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

$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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. I just got to a similar conclusion. More precisely $\lceil 2\sqrt{N} - 1 \rceil$. $\endgroup$ – Muhammad R. Soliman May 2 '19 at 0:11
  • $\begingroup$ Could you please explain why $L_{i+1} = L_i +1$ when $L_{i} < \sqrt{N}$? $\endgroup$ – Muhammad R. Soliman May 2 '19 at 12:41
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan May 2 '19 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.