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
    It minimum, you require $\gcd(d_1,d_2)$ to be a divisor of $a_1-b_1$.2012-11-05
  • 0
    If a1-b1 is divisible by gcd(d1, d2), then there is a solution. If not, there isn't. I have a equivalent check in my program. But still, I don't know how to speed it up using this. (I hope I understood you right)2012-11-05
  • 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
    Wonderful answer. Thank you for that. I have a question regarding the last step. Say I have the last-but-one matrix. Do I understand it correctly that now I am trying to combine the two rows into one, where the first two numbers would be minimal, but positive?2012-11-06
  • 0
    Is it somehow possible for this algorithm not only to calculate the first term, but also the following? I have several different sequences and I need to find a term they all contain. So I was thinking that I would be able to quickly calculate terms that two sequences contain and then check them against the remaining sequences. This is kinda brute force, but not as slow as checking _all_ the terms. (the next common term for the example given is 1352)2012-11-06
  • 0
    @Martin yes to the minimal but positive. The row 16 3 0 shows that wherever the sequences are equal, count another 16 on one and 3 on the other and they are equal there also. And another 16 and 3 to find the next one after that, etc.2012-11-09
  • 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