Combining 2 arithmetic sequences into one [duplicate]

Suppose we have two arithmetic progressions, e.g:

$${a_{n}=a_{1}+(n-1)d}$$ $${b_{n}=b_{1}+(n-1)e}$$

How do we find a non-recursive formula for nth member of progression $c_{n}$ such, that it is a strictly growing union of $a_{n}$ and $b_{n}$ with no duplicates? For example, for the following arithmetic progressions:

$${a_{n}=6n}$$ $${b_{n}=8n}$$ $${c_{n}=?}$$

Then $c_{n}$ should yield the following sequence: $0, 6, 8, 12, 16, 18, 24, 30, ...$

Solution 1:

So we are given the two sequences $$ \bbox[lightyellow] { a_{\,n} = a_{\,1} + \left( {n - 1} \right)d\quad b_{\,n} = b_{\,1} + \left( {n - 1} \right)e\quad \left| {\;1 \le n} \right. } $$

When drawn on the cartesian plane, taking $n$ to be continuous, they will correspond to two lines, which
will cross each other at $n = \left( {b_{\,0} - a_{\,0} } \right)/\left( {d - e} \right)$, which may be either negative or non-negative.

Let us assume for the moment that it be negative, and let us rearrange the sequences to start at $n=0$, which much simplifies the following arguments.
Without loss of generality, we can assume $a_{n} \le b_{n}$.

So we are considering: $$ \bbox[lightyellow] { \left\{ \matrix{ a_{\,n} = a_{\,0} + d\,n \hfill \cr b_{\,n} = b_{\,0} + e\,n \hfill \cr} \right.\quad \left| \matrix{ \;0 \le n \hfill \cr \;0 \le a_{\,0} \le b_{\,0} \hfill \cr \;0 \le d \le e \hfill \cr} \right. } \tag{1} $$ also assuming that all the parameters be integers, because if they were rationals we can always multiply by their LCM and reconduce ourselves to the above.

The two sequences will produce the same result $a_{n}=b_{m}$ $$ \bbox[lightyellow] { a_{\,0} + d\,n = b_{\,0} + e\,m\quad \Rightarrow \quad d\,x + e\,y = b_{\,0} - a_{\,0} } \tag{2} $$ when and if the indicated corresponding Bezout's Identity has solutions, which depends on the $\gcd$'s of the parameters.

• 2.a) If there is a solution ($\gcd{(e,d)}$ divides $ b_{\,0} - a_{\,0}$), call it $\left( {n^ * ,m^ * } \right) = \left( {x^ * , - y^ * } \right)$, then they will repeat infinitely as $\left( {n^ * ,m^ * } \right) + k\left( {e,d} \right)$;
• 2.b) if there is not ($\gcd{(e,d)}$ does not divide $ b_{\,0} - a_{\,0}$), then the two sequences are never including the same value.

That premised, the problem requires to merge the two sequences into a single increasing one, $c$.

We have assumed $a$ to be lower than $b$, then $c$ will start as $$ \bbox[lightyellow] { c = \left\{ {a_{\,0} ,a_{\,0} + d1, \cdots ,a_{\,0} + d\,q_{\,0} } \right\} = \left\{ {a_{\,0} ,a_{\,1} , \cdots ,a_{\,q_{\,0} } } \right\} } $$ and we make a stop at $a_{\,0} + d\,q_{\,0} $ that is at the maximum index of the $a$ sequence for which $$ \bbox[lightyellow] { a_{\,0} + d\,q_{\,0} < b_{\,0} \quad \Rightarrow \quad q_{\,0} = \left\lceil {{{b_{\,0} - a_{\,0} } \over d}} \right\rceil - 1 = \left\lfloor {{{b_{\,0} - a_{\,0} - 1} \over d}} \right\rfloor } $$

Thereafter we insert $b_0$ (the ceiling assures that it is not a duplicate of the precedent $a$ sequence) and continue $$ \bbox[lightyellow] { \displaylines{ c = \left\{ {a_{\,0} ,} \right.a_{\,1} ,\;\; \cdots \;\;,a_{\,q_{\,0} } , \cr \quad b_{\,0} ,a_{\,q_{\,0} + 1} , \cdots ,a_{\,q_{\,1} } , \cr \quad b_{\,1} ,\; \cdots \cr \quad \quad \vdots \cr \left. {\quad b_{\,d - 1} ,a_{\,q_{\,d - 1} + 1} , \cdots ,a_{\,q_{\,d} } } \right\} \cr} } \tag{3} $$ where $$ \bbox[lightyellow] { q_{\,k} = \left\lceil {{{b_{\,0} - a_{\,0} + k\,e} \over d}} \right\rceil - 1 = \left\lfloor {{{b_{\,0} - a_{\,0} - 1 + k\,e} \over d}} \right\rfloor } $$

However it may happen that $a_{\,q_{\,k} + 1}=b_{k}$, when $$ \bbox[lightyellow] { \eqalign{ & b_{\,k} = b_{\,0} + ke = a_{\,q_{\,k} + 1} = a_{\,0} + d\left\lceil {{{b_{\,0} - a_{\,0} + k\,e} \over d}} \right\rceil \quad \Rightarrow \cr & \Rightarrow \quad {{b_{\,0} - a_{\,0} + ke} \over d} = \left\lceil {{{b_{\,0} - a_{\,0} + k\,e} \over d}} \right\rceil \quad \Rightarrow \cr & \Rightarrow \quad b_{\,0} - a_{\,0} + k\,e \equiv 0\quad \left( {\bmod d} \right)\quad \Rightarrow \cr & \Rightarrow \quad \left( {\,q_{\,k} + 1,k} \right) \in \left\{ {{\rm solutions}\,{\rm of}(2)} \right\} \cr} } \tag{4} $$ and we shall cancel either $b_k$ or $a_{\,q_{\,k} + 1}$.

We have broken the sequence in (3) just before $b_d$, since: $$ \bbox[lightyellow] { \left\{ \matrix{ q_{\,d} = \left\lfloor {{{b_{\,0} - a_{\,0} - 1 + d\,e} \over d}} \right\rfloor = q_{\,0} + e \hfill \cr b_{\,d} = b_{\,0 + d} \hfill \cr a_{\,q_{\,d} + 1} = a_{\,0} + d\left\lfloor {{{b_{\,0} - a_{\,0} - 1 + d\,e} \over d}} \right\rfloor = a_{\,q_{\,0} + 1 + e} \hfill \cr} \right. } \tag{5} $$

and thus in the partial sequence shown in (3), the subsequence starting with $b_0$ repeats adding $d$ to the $b$ indices and $e$ to the $a$ indices, and that repeats indefinitely.
Note that in the starting partial $c$, there can be only one (if any) double entry, and it shall be in the second part. The cancelled double entry (if there was) remains cancelled in the repetition.

So we defined an algorithm to construct the sequence $c$.
It is clear that the algorithm is valid also if we choose a starting $n=n_0$ different from 0, either positive and negative, so that the initial assumption concerning the crossing point of the two lines is inessential.

Because of the nature of the expression for $q_k$, it is in general not possible (it has not yet been found) to capture it into a formula.