Abhibansal53's blog

Least common term of two arithmetic sequences
By Abhibansal53, history, 9 years ago, In English

Given two arithmetic sequences (a1,d1 i.e. first term and common difference of first sequence and similarly a2,d2),what is the best algorithm to tell whether they have any common term,and if yes then tell the lowest one.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's say a[x]=b[y]. Then a1+d1*x=a2+d2*y or d1*x-d2*y=a2-a1. So, you just need to solve Diophantine equation.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I knew this method.I was wondering if there is any other way.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this can be done with the Chinese Remainder Theorem. A term in both sequences is congruent to a1 (mod d1) and to a2 (mod d2), so you can find a number x such that any common term must be equal to x (mod lcm(d1, d2)) using Chinese Remainder Theorem (assuming there is at least one common term). Then, you can take the smallest value with that mod value that is greater than or equal to max(a1, a2).

→ Reply