3
$\begingroup$

Formula to find the first intersection of two arithmetic progressions

I am not good in math, but I need to determine if two generic arithmetic progressions have an intersection point and, in that case, find the first intersection. I've searched the web and found some solutions, but I couldn't understand them.

Is it possible to have a simple formula or algorithm that finds the first intersection point of two arithmetic progressions?

Example 1:

$$ A_n = A_1 + (n - 1)d \\ AP1: A_1 = 1, d = 14 \Rightarrow \{1, 15, 29, 43, \dotsc \} \\ AP2: A_1 = 8, d = 21 \Rightarrow \{8, 29, 50, 71, \dotsc \} \\ $$ Result: First intersection point on $A_n = 29$

Example 2: $$ A_n = A_1 + (n - 1)d \\ AP1: A_1 = 1, d = 14 \Rightarrow \{1, 15, 29, 43, \dotsc \} \\ AP2: A_1 = 8, d = 28 \Rightarrow \{8, 36, 64, 92, \dotsc \} $$ Result: Does not have an intersection point

The reason I need this is because I am developing a calendar (like Google Calendar) but where it is not allowed to create two event series that intersect each other. I've posted a similar question here.

$\endgroup$
3
$\begingroup$

Assume the two progressions are $$ A_n = A_1 + (n-1) \, d \\ B_m = B_1 + (m-1) \, D $$

You want to check \begin{align} A_n &= B_m \\ A_1 + (n-1) \, d &= B_1 + (m-1) \, D \iff \\ A_1 - B_1 + D - d &= -n \, d + m \, D \iff \\ -d \, n + D \, m &= A_1 - B_1 + D - d \quad (1) \end{align}

Interpretation as Linear Diophantine Equation

Equation $(1)$ can be interpreted as a linear Diophantine equation $$ a X + b Y = c \quad (X, Y \in \mathbb{Z}) \quad (2) $$ with $a = -d$, $b = D$ and $c = A_1 - B_1 + D - d \in \mathbb{Z}$ and variables $X = n$ and $Y = m$, where one is only interested in the positive solutions $X > 0, Y > 0$.

For this kind of equations there exists an algorithm to determine the solutions.

Criterion for Solutions:

For solutions to exist, one needs $g = \gcd(a, b)$ to divide $c$, $g \mid c$. Here we have $$ g = \gcd(-d, D) = \gcd(d, D) $$ So the criterion for a solution is $$ \gcd(d, D) \mid A_1 - B_1 + D - d \quad (3) $$ Because $\gcd(d, D) \mid D - d$, it suffices to check $$ \gcd(d, D) \mid A_1 - B_1 \quad (4) $$

Solution of the Homogeneous Equation:

The homogeneous equation $a X_h + b Y_h = 0$ has the solutions $$ (X_h,Y_h) = (t \, b', -t\, a') \quad (t \in \mathbb{Z}) \quad (5) $$ with $a' = a / g = -d / \gcd(d,D)$, $b' = b / g = D / \gcd(d, D)$.

Finding one Particular Solution:

A particular solution of $(2)$ is usually found by finding a solution $(u, v)$ to $$ a u + b v = g \iff \\ -d u + D v = \gcd(d, D) $$ these numbers are calculated by the extended Euclidean algorithm for $-d$ and $D$.

A particular solution is $$ (X_p, Y_p) = \left(\frac{c}{g} u, \frac{c}{g} v \right) \quad (6) $$

General Solution:

The general solution is: \begin{align} (X, Y) &= (X_h + X_p, Y_h + Y_p) \\ &= \left(\frac{c}{g} u + t \, b', \frac{c}{g} v -t\, a' \right) \\ &= \left(\frac{c}{g} u + t \, \frac{D}{g}, \frac{c}{g} v + t\, \frac{d}{g} \right) \quad (7) \end{align}

Reducing to the First Positive Solution:

We need to choose a $t$ with $$ X(t) = \frac{c}{g} u + t \, \frac{D}{g} > 0 \\ Y(t) = \frac{c}{g} v + t\, \frac{d}{g} > 0 $$ Among those $t$ one needs to choose the one which minimizes $(X,Y)$: $$ t = \max \left\{ \left\lfloor -\frac{c}{D} u \right\rfloor + 1, \left\lfloor -\frac{c}{d} v \right\rfloor + 1 \right\} \quad (8) $$

Example:

For your first example we had $A_1 = 1$, $B_1 = 8$, $d = 14$, $D = 21$.

We have $g = \gcd(14, 21) = 7$. The extended Euclidean algorithm gives (e.g. see here) $$ (u, v) = (1, 1) \\ -14 \, 1 + 21 \, 1 = 21 - 14 = 7 = \gcd(14, 21) $$ We have $c = 1 - 8 + 21 - 14 = 0$, so we have just a homogenous equation here. The solution is $$ (X_h, Y_h) = (t b', -t a') = (t (21/7), -t(-14/7)) = (3 t, 2 t) \quad (t \in \mathbb{Z}) $$ These are all integer solutions. The first positive solution happens for $t = 1$ with $$ (X, Y) = (3, 2) = (n, m) $$ and indeed $$ A_3 = 1 + (3-1) \cdot 14 = 1 + 2 \cdot 14 = 29 \\ B_2 = 8 + (2-1) \cdot 21 = 8 + 21 = 29 $$

$\endgroup$
  • $\begingroup$ In my first example, A1=1, d=14, B1=8, D=21. In your formula it would be: (|21-14|) | 1 - 8 + 21 - 14 => 7 | 0. What does it mean? $\endgroup$ – Vini Feb 15 '16 at 2:08
  • 1
    $\begingroup$ That is fine. $0 = k \cdot 7$ for $k = 0 \in \mathbb{Z}$. so $7 \mid 0$ is true and this says there are solutions $X = n \in \mathbb{Z}$ to $(2)$ and its special case $(1)$. $\endgroup$ – mvw Feb 15 '16 at 2:23
  • $\begingroup$ Ok, so 7 | 0 means that 0 is multiple of 7. I didn't know what this symbol mean. Let me try the second example... A1=1, d=14, B1=8, D=28 => (|28-14|) | 1-8+28-14 => 14 | 7 => k=0.5 not Z, so false $\endgroup$ – Vini Feb 15 '16 at 2:34
  • 1
    $\begingroup$ Reading again. Yes. It means $7$ divides $0$ with remainder $0$. The second case runs down to if $14$ divides $-7$, or $14$ divides $7$. Which in both cases it does not. $\endgroup$ – mvw Feb 15 '16 at 2:35
  • $\begingroup$ It is great to be able to check if the progressions overlap without using GCD. Is it also possible to find the first overlap occurrence? $\endgroup$ – Vini Feb 15 '16 at 3:07
2
$\begingroup$

Let the two series be $ a[n] = p + nq $ and $ b[n] = r + ns $

Assuming it does intersect, then

$ a[x] = b[y] \implies p + xq = r + ys $

It looks daunting with so many variables, but in fact $ p, q, r, s $ are all known, so not too bad. Next we rearrange

$ p - r = ys - xq $. By the extended euclidean algorithm, we know we can find $ x $ and $ y $ such that $ ys - xq = gcd(s, q) $.

So the two series intersect if and only if $ p - r $ is a multiple of $ gcd(s, q) $.

To code the algorithm, just compute the gcd and do a trial division.

$\endgroup$
  • $\begingroup$ Ok, thanks. I can compute the gcd(s,q). After testing that p - r is a multiple of gcd(s,q), is there a formula that I can find the first intersection, or do I need an algorithm with a loop? $\endgroup$ – Vini Feb 15 '16 at 1:19
  • 1
    $\begingroup$ Using the extended euclidean algorithm, you could find the value of x and y, that should lead you to an intersection point. $\endgroup$ – Andrew Au Feb 15 '16 at 6:56

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.