title: Finding common elements (intersections) between arithmetic progressions with different variables
body: <p>This question could be posted as a math question, but since I want to implement this I thought this would be a better place.</p>
  
  <p>I have a problem I need solve and I'm trying to solve it the best way possible.</p>
  
  <p>I have two units and I want to predict when these units will reach a determined point and meet. These units move in a circular/elliptic fashion, and the equation that predicts when each unit will reach the point is easily calculable. The time is discrete, meaning the system works in ticks, so we have times = t0, t1, t2, ... and so on.</p>
  
  <p>So the example is this, let's call the point they will meet P.</p>
  
  <p>Unit 1 has two equations, so for any x, t is the time when Unit 1 will be on P.</p>
  
  <pre><code> t = 10x + 1
   t = 10x + 9
  </code></pre>
  
  <p>Unit 1 will be on P at: 1, 9, 11, 19, ...</p>
  
  <p>Same for Unit 2:</p>
  
  <pre><code> t = 6y + 1
   t = 6y + 5
  </code></pre>
  
  <p>Unit 1 will be on P at: 1, 5, 7, 11, 17, ...</p>
  
  <p>So at t = 11, the Units will meet at P. There could be more meeting times, but only one happened.</p>
  
  <p>Since these equations may generate an infinite number of meeting times, a time limit is introduced, let's call this time limit L. So given those equations I want to calculate all the times (ticks) that are less than L where the units meet each other.</p>
  
  <p>Note that we could build a sorted list/array for each pair of equations and calculate the intersection, but I think this could be solved in a smarter way.</p>
  
  <p>How can we solve this using the equations? Is it possible or do we really need to build the arrays?
   What is the lower bound for this problem? Can this be done in O(1)? What if we add some restrictions to the problem, can we make it work in O(1)? Like, if we only wanted to know the first meeting time, or any one meeting time.</p>
  
  <p>I believe this is gonna end up in O(L), since we have two sorted array of size at most L, and we can get the intersection in one pass through each array.</p>
  
  <p>Mods, feel free to correct english errors, it's not my main language.</p>