-1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Does your answer go all the way to the ends 2998,3001,4001 for the count of 0nly 6 common terms? $\endgroup$ – coffeemath Dec 5 '16 at 15:15
  • $\begingroup$ its 6 for only the given example $\endgroup$ – psil123 Dec 5 '16 at 15:16
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ suppose i have n series with common differences a1,a2,...,an and each of them have the starting number as 1 . How can i find the number of common terms ? $\endgroup$ – psil123 Dec 5 '16 at 15:17

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.