0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – lulu Sep 22 '18 at 22:15
  • $\begingroup$ @lulu i have edited my answer. Under number line i mean number line of positive integers $\endgroup$ – blindProgrammer Sep 22 '18 at 22:32
  • $\begingroup$ I think usage of the word "consecutive" might make this question clearer, if I'm interpreting it correctly. $\endgroup$ – Carl Schildkraut Sep 22 '18 at 23:34
  • $\begingroup$ 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$. $\endgroup$ – lulu Sep 22 '18 at 23:47
  • $\begingroup$ @lulu I imagine that's a typo - in the list the triple $\{2,3,4\}$ is clearly marked. $\endgroup$ – Carl Schildkraut Sep 22 '18 at 23:47
1
$\begingroup$

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}$$

$\endgroup$

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.