Algorithm with GCD and LCM

Question

I am trying to build an algorithm to solve a simple problem. I get two signals over and over at once and I need to found out when they synchronize.

The sequence is coded as a=1, b=2, c=4, d=8,... y=2^24, z=2^25, there is a sign of | which means end of a message.

For example:

• ea|babab -> whole sequence is bababea
• d|abaca -> whole sequence is abacad

Therefore the first sequence has offset of e+a=16+1=17 and the whole message is bababea = 2+1+2+1+2+16+1 = 25 long. The second sequence has offset of d=8 and the whole message is abacad = 1+2+1+4+1+8 = 17 long.

They sync in time 42 because 17+25 and 8+17+17 equals 42.

I do know that it has something to do with LCM and GCD but I can't find the formula.

The formula of offset1 + lenght1*x = offset2 + lenght2*y takes too long in the computer if done with for loop, therefore I am trying to find a better way to solve this.

Can you please help? Thank you.

Answer 1

Reverse engineering your post, I think the relevant arithmetic problem is:

You are given four positive integers, $a,b,c,d$. Find the smallest nonegative integers $x$ and $y$ such that $$ a + bx = c + dy$$

(I see that you have edited something similar into your post)

---

To solve this, suppose $c \geq a$ (if not, solve the problem the other way around). We can naively solve for $x$:

$$ x = \frac{c-a+dy}{b} $$

however, that is an integer only if the numerator is divisible by $b$. So, we need to solve the modular equation

$$ c - a + dy \equiv 0 \pmod{b} $$

for $y$. Then, the answer we're looking for is obtained by taking the smallest nonnegative solution for $y$. The corresponding value for $x$ is obtained by plugging into the formula above.

(of course, it turns out that you actually just want the value $c+dy$ from the solution, so you don't have to compute $x$)

How to solve a modular equation is beyond the scope of this post, but should be easy to search for.