1
$\begingroup$

While working on linked question, I encountered recurrence relation of form: $$ a_{n+2}=a_n\operatorname{mod}a_{n+1},\quad a_0=A,\quad a_1=B, $$ where $A,B-$positive integers, $A<B$.

I wonder if there exists a technique to get general term, few terms before $a_n$ turns into $0$, or at least number of iterations before $a_n$ turns into $0$.

$\endgroup$
  • 1
    $\begingroup$ It looks a lot like Euclide's algorithm $\endgroup$ – Vincent Sep 20 '16 at 15:23
1
$\begingroup$

Your sequence is basically the intermediate results from the Euclidean algorithm applied to $A, B$. There's no "general term", it is very easy to calculate the terms, and for the number of nonzero elements in the sequence, you can e.g. read What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?

$\endgroup$

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.