Finding the minimum number of additions needed to exceed a number $n$ We are given $3$ integers, $a, b,$ and $n$. At each stage, we can either add $a$ to $b$ or add $b$ to $a$ so that the chosen (only $1$ of them) variable that we will add to will have a new value of $a + b$.
We are asked to find the minimum number of such additions we need so that, at some point, either $a$ or $b$ exceeds $n$.
I tried to simulate a process in which we add $a$ to $b$, then $b$ to $a$, then $a$ to $b \ldots$ etc, but it is taking too much time, and even sometimes it's not the optimal answer. (Sometimes we are better off just continuously adding $1$ of them to the other).
I would really appreciate any hints/solutions. Thank you.
 A: Let $t(a,b,n)$ denote the number of steps until $\max\{a,b\}\geq n$.
One way to define $t(a,b,n)$ is by the recursion
$$
t(a,b,n) = \min\{t(a+b,b,n), t(a+b,a,n)\} + 1
$$
with the condition that $t(a,b,n) = 0$ when $\max\{a,b\}\geq n$.
Let us introduce a partial ordering on the pairs $(a,b)$ so that
$(a',b')\leq (a,b)$ whenever either $a'\leq a$ and $b'\leq b$ OR $a'\leq b$ and $b'\leq a$.
The key observation is that
$$
t(a',b',n) \geq t(a,b,n)
$$
when $(a',b')\leq (a,b)$ (this holds when $\max\{a,b\}\geq n$, and then to see it holds for all $(a,b)$ you can induct backwards using the recursion relation).  Now the point is to define the greedy map
$$
F(a,b) = \begin{cases}
(a+b,b), &b\geq a \\
(a, a+b), &b < a.
\end{cases}
$$
The point of $F$ is that it satisfies
$$
(a+b,b) \leq F(a,b)
$$
and
$$
(a,a+b)\leq F(a,b).
$$
This allows us to rewrite the recursion relation for $t(a,b,n)$ as
$$
t(a,b,n) = t(F(a,b), n) + 1.
$$
Notice that iterating $F$ results in the alternating map you described.  To see this, consider for example the case $a=1$ and $b=5$.  The first few steps are $(1,5)\to (6,5)\to(6,11)\to(17,11)$.
This answer is getting a little long, but one thing that should happen is that $b/a$ will approach the golden ratio $\phi$ (or its reciprocal), and asymptotically the values at the $n$-th step should grow like $\phi^n$.  Thus as a very rough approximation (for very large $n$) one has
$$
t(a,b,n) \approx \log(n) / \log(\phi).
$$
A: Let
$$S = (x,y) |\space \space x,y \in I^+  \space \cup \space ax + by \ge n \}$$
$Foreach \space (x,y) \in S$
$Let$
$$ t[0] = \max(x,y)$$
$$ t[1] = \min(x,y)$$
$$ j = 2 $$
$$ s=0 $$
$$ m= +\infty $$
$\space \space\space\space\space\space\space\space\space\space\space\space\space
while \space t[j] \ne 0$
$\space \space\space\space\space\space\space\space\space\space\space\space\space do
$
$\space \space\space\space\space\space\space\space\space\space\space\space\space s++
$
$$ t[j] = |t[j-1] - \min(t[j-2], t[j-3])| $$
$\space \space \space \space \space \space \space \space \space \space\space\space\space\space\space\space\space\space\space\space\space if \space t[j] = 0$
$\space \space \space \space \space \space \space \space \space 
\space \space \space \space \space \space \space \space \space \space\space\space\space\space\space\space\space\space\space\space\space if \space t[j-1] = 1 and\space  t[j-2] = 2$
$\space \space \space \space \space \space \space \space \space 
\space \space \space \space \space \space \space \space \space 
\space \space \space \space \space \space \space \space \space \space\space\space\space\space\space\space\space\space\space\space\space \space m = \min (m, s)$
$\space \space \space \space \space \space \space \space \space 
\space \space \space \space \space \space \space \space \space 
\space \space \space \space \space \space \space \space \space \space\space\space\space\space\space\space\space\space\space\space\space \space s=0$
$m$ will hold the value of the minimum number of steps.
For solutions where the sum of $a$ and $b$ equals n, this solutions is fast. When there is no match you must add $(x + 1, y), (x, y + 1)$ to the solution set and rerun. This will be slower.
This is a good start. It would be helpful if we could create a function of coefficients $(x,y)$ that would fit the description of the summations.
$(1,2)$ for $a + 2b$
$(5,3)$ for $5a + 3b$
$(4,1)$ for $4a + b$
$2a + 2b$ would be impossible. If we could change the algorithm to exclude those sets of coefficients that are impossible, the solution would run quicker.
