# Can i find largest sequence of multiples of given n positive greater than 1 integers?

Suppose i have $$n$$ positive $$q_i>1, i\in\{1,2\dots n\}$$ integers. The multiples of these $$q_i>1$$ integers form sequences on number line with length $$l\geqslant1$$. My question is: Is it possible, for given $$q_i>1$$ integers to calculate maximum possible value for $$l$$? I do not want to use "brute-force" type approach. What would be most efficient way doing it?

If it simplifies the problem, one can also assume that $$q_i>1$$ integers are coprime.

For example: Suppose $$n=2, q_1=2, q_2=3$$ the sequences of multiples (I denote valid sequences with curly braces) of $$q_1\ and \ q_2\ are \ \{0\},1,\{2,3,4\},5,\{6\},7,\{8,9,10\},11,\{12\}\dots$$ As you can see from example, the available values for $$l$$ are finite, because they repeat themselves after $$6,12\dots$$ The Longest sequence is $$\{1,2,3\}, \{8,9,10\}\dots$$ and I expect the answer of $$l$$ to be $$3$$

• Not following. What causes the sequence(s) to terminate? Why aren't there infinitely many members of each sequence? Perhaps it would help if you gave an explicit example. Say $q_1=2,q_2=3$. What's the answer you want in that case and why? – lulu Sep 22 '18 at 22:15
• @lulu i have edited my answer. Under number line i mean number line of positive integers – blindProgrammer Sep 22 '18 at 22:32
• I think usage of the word "consecutive" might make this question clearer, if I'm interpreting it correctly. – Carl Schildkraut Sep 22 '18 at 23:34
• How is $\{1,2,3\}$ an example? If you are looking for consecutive strings of multiples, then $\{2,3,4\}$ would be an example for $q_1=2,q_2=3$. Indeed, it is clear that you can't have a sequence of length $4$ since no two consecutive odd numbers are both multiples of $3$. – lulu Sep 22 '18 at 23:47
• @lulu I imagine that's a typo - in the list the triple $\{2,3,4\}$ is clearly marked. – Carl Schildkraut Sep 22 '18 at 23:47

If the $$q_i$$ are coprime the pattern will repeat after the product of all the $$q_i$$, so if you are doing brute force you can stop there. In your example with $$2,3$$ you could stop after $$6$$ and know you have the longest consecutive sequence.
You can do better, but it is hard to describe as an algorithm. Let's say we have the $$q_i 2,3,5,13$$. This will not repeat until $$390$$. We can make a row $$2\_2\_2\_2\_2\_2\_2\_2\_2\_2\_2\_2\_2\_2\_2\_2\_2$$ which shows that $$2$$ divides every other number but the alternate ones are not accounted for yet. Now fill in a blank with $$3$$ and note that it will repeat every $$6$$. There is another multiple of $$3$$ in the middle, but that number is already a multiple of $$2$$. That gives $$232\_2\_232\_2\_232\_2\_232\_2\_232\_2\_232$$ Now we note that the $$5$$s will come $$10$$ apart and there are always at least two blanks between them. Putting a $$5$$ in the blank right after a $$3$$ makes the next occurence of $$5$$ land on a $$3$$, so we wait one. We can only fill one of those with a $$13$$, so it becomes $$232(13)25232\_2\_23252\_232\_2\_232\_2\_232$$ which shows we can get nine numbers in order with this set. The Chinese remainder theorem guarantees this pattern exists somewhere because the first number is the solution to $$n\equiv 0 \pmod 2\\n\equiv 2 \pmod 3\\n\equiv 0 \pmod 5\\n \equiv 10 \pmod {13}$$