2
$\begingroup$

I have a problem which could be simplified as: there are two arithmetic sequences, a and b. Those can be written as

a=a1+m*d1 b=b1+n*d2 

I need to find the lowest term, appearing in both sequences. It is possible to do by brute force, but that approach is not good enough. I was given a hint - extended Euclidean algorithm can be used to solve this. However, after several frustrating hours I cannot figure it out.

For example:

a1 = 2 d1 = 15  b1 = 67 d2 = 80  That gives these sequences   2 17 32 47 62 77 ... 227 ...               67  147  227                         ^                    Needed term 

Could you somehow point me to how to use the algorithm for this problem? It's essentially finding the lowest common multiple, only with an "offset"

Thank you

  • 0
    (+1) because your example helped me to give you a (hopefully) clear answer.2012-11-05

1 Answers 1

1

Your equations: $a(m) = a_1 + m d_1$ $b(n) = b_1 + n d_2 $

You want $a(m) = b(n)$ or $a(m)-b(n)=0$, so it may be written as $(a_1-b_1) + m(d_1) +n(-d_2) = 0$ or $ m(d_1) +n(-d_2) = (b_1-a_1) $

You want $n$ and $m$ minimal and that solves that. This is of course very similar to the EGCD, but that the value of $b_1 - a_1$ is the desired value intead of the value $1$. EGCD sovles it for the value of $1$ (or the gcd of $d_1$ and $d_2$).

This is actually a lattice reduction problem since you are interested in the minimum integer values for $m$ and $n$. That is an involved problem, but this is the lowest dimension and thus is relatively easy.

The method I have written in the past used a matrix form to solve it. I started with the matrix $\pmatrix{1 & 0 & d_1 \\ 0 & 1 & -d_2}$

which represents the equations \begin{align} (1)d_1 + (0)(-d_2) = & \phantom{-} d_1 \\ (0)d_1 + (1)(-d_2) = & -d_2 \\ \end{align}

Each row of the matrix gives valid numbers for your equation, the first element in the row is the number for $m$, the second is for $n$ and the third is the value of your equation for those $m$ and $n$. Now if you combine the rows (such as row one equals row one minus row two) then you still get valid numbers. The goal then is to find a combination resulting in the desired value of $b_1 - a_1$ in the final column.

If you use EGCD you can start with this matrix: $\pmatrix{d_2 \over g & d_1 \over g & 0 \\ u & -v & g}$

where $u$, $v$, and $g$ are the outputs of the EGCD (with $g$ the gcd) since EGCD gives you $ud_1 + vd_2 = g$

In your example you would have: $\pmatrix{16 & 3 & 0 \\ -5 & -1 & 5}$ From there you can scale the last row to get $kg = (b_1 - a_1)$ for some integer $k$, then to find the minimal values use the first row to reduce, since the zero in the first row will not affect the result.

Again, for your example, $k=13$ which gives $\pmatrix{16 & 3 & 0 \\ -65 & -13 & 65}$

Adding $5$ times the first row gives $\pmatrix{15 & 2 & 65}$

Which represents the $16$th and $3$rd terms (count starts at $0$) respectively.

  • 0
    @Martin if you have more than two sequences, then it becomes more involved, the comment I made about lattice reduction becomes more important. If you have three or more sequences, then there are two or more homogenous rows to be able to combine (the 16 3 0 in your example). But yes, doing for two first does reduce some work. Could you not just define a sequence from where the two are equal then combine that with the next sequence and so on?2012-11-09