Is there a closed-form for the following recurrence, if yes, how to find it? $$ f(a,x) = \begin{cases} \text{$1$,} &\quad\text{$a\le x$}\\ \text{$1+f(2(a-x),2*x)$} \end{cases} $$ You can consider the constraints, if necessary, as $1\le a,x\le 10^9$.
Motivation: I want to calculate the no. of times this operation needs to be applied while $a>x$. To do so, I wrote a simple recursive function in code, which seems to work fast. Hence, I was wondering if a closed-form (formula) exists for this.
Code:
int count (int b, int x) {
if (b <= x) return 1;
return 1+count(2*(b-x),2*x);
}
Based on your code snippet I've assumed the problem is for $a,x$ integers. Playing around with small values and fixed $a$ or $x$, you might notice that the sequence $f(a,1)$ is just $1,2,3,\dots$, sequence $f(a,2)$ is $1,1,2,2,3,3,\dots$, and so on. This suggests the result will be "close" to $\lfloor a/x \rfloor$ (where $\lfloor .\rfloor$ is the floor function). After adjusting the starting values, we can see that $$f(a,x)=\left\lfloor \frac{a-1}{x}\right\rfloor+1.$$
To be sure this works for all integers $a,x$, you should prove that it matches the original definition. For $a \leq x$ this is simple, we have $a-1<x$, hence $\left\lfloor \frac{a-1}{x}\right\rfloor=0$ and so $f(a,x)=1$. For $a>x$, we need to verify the $f(a,x)=1+f(2(a-x),2x)$. For this, consider $a=rx+q$ with integers $r,q$, $q<x$, the problem then simplifies (again using $\lfloor m/n \rfloor=0$ for $0\leq m<n$).