Finding common terms of two or more arithmetic sequences

Question

Suppose I have three sequences $\{1,4,7,....,2998\}$ , $\{1,3,5,7,9,11,....,3001\}$ and $\{1,6,11,....,4001\}$ .

How can i find the number of common terms among them ?

For Example ,

If I have

1,3,5,7,9,11,13,15,17 and 19

1,4,7,10,13,16 and 19

1,6,11 and 16

My answer would be $6$.

Suppose i have $n$ number of series' with common differences $a_1,a_2,...,a_n$ and each of them having the starting term as $1$ . How can i find the number of common terms then ?

Answer 1

Write the arithemtic sequence in form: $a_n = a_0 + (n-1)d_1, b_n = b_0 + (n-1)d_2, c_n = c_0 + (n-1)d_3$. Now if they have a common term then we can write:

$$x = a_0 + kd_1 = b_0 + sd_2 = c_0 + td_3$$

As the common difference is known we can write this as:

$$x \equiv a_0 \pmod {d_1}$$ $$x \equiv b_0 \pmod {d_2}$$ $$x \equiv c_0 \pmod {d_3}$$

This is system of linear congurence relations and it can be easily solved by the Chinese Remainder Theorem.

And once you find one common element, to find the next common element you just add $LCM[d_1,d_2,d_3]$ to the previous one. In fact if you get $x \equiv A \pmod{LCM[d_1,d_2,d_3]}$ when solving the system of congurences, then total number of elements should be:

$$1 + \left\lfloor\frac{K-A}{LCM[d_1,d_2,d_3]}\right\rfloor$$

where $K$ is the smallest last element in the arithemtic sequences.

Answer 2

If you at the explicit form of your sequences, which build your sets, you get get that $a_n = 1+3 \cdot n$, $b_n = 1+ 2 \cdot n$ and $c_n =1+5 \cdot n$.

Now you just have to find the least common multiple of 2,3 and 5 and see that all their common terms are $c_n = 1 + 30 \cdot n$