About consecutive integers covered by arithmetic progressions

Question

Help me please to solve the following problem.

There are $n$ arithmetic progressions of the form:

$$(2i+1)k + x_i,~~~~ i = 1,\ldots,n, k \geq 0$$

Initial integer terms $x_i \geq 0$ are varying.

The problem is to cover $m(n)$ - the maximum possible number of consecutive integers starting with $ 1 $ (the number is covered, if it belongs to at least one of these progressions).

For example, is it true, that: $$m(n) \approx \operatorname*{LCM}\limits_{i=1,\,\ldots\,,\,n}(\{2i+1\}) \text{?}$$

But it is so much and I am in search of the best solutions for this problem.

Numerical simulation shows something like this: $m(n) \approx Cn$

Update: Thank you for your answers! I did not imagine that it is so difficult problem.

Question: What is known about bounds of $m(n)$?

Is it proposition about upper bound whether true or not:

For fixed integer $k \geq 0$, and for all integers $x_i$ perform:

If $$u = \operatorname*{LCM}\limits_{i=1,\,\ldots\,,\,n}(\{(2i+1)k+x_i\})+1$$

Then number $u$ is not belong to any of $n$ arithmetic progressions of the form: $(2i+1)k+x_i,~~~i = 1,\ldots,n$ ?

It seems to me that it is obviously true.

Answer 1

Not only is no upper bound known, it is unknown whether $m(n)$ can be infinite. It is a well-known open conjecture of Erdős and Selfridge that there does not exist an incongruent covering system whose moduli are all odd numbers $> 1$. A counterexample to that conjecture would be a finite set of a.p.'s with distinct odd differences that cover all of $\mathbb N$ (and would be worth \$900 from Selfridge).

EDIT: Using depth-first search for $n \le 10$ and Cplex after that, I find that the first few $m(n)$ are as follows:

$$ \matrix{n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\cr m(n) & 1 & 2 & 4 & 6 & 10 & 13 & 17 & 22 & 30 & 38 & 45 & 53 & 63 & 74 & 83 & 96\cr} $$ The sequence doesn't appear to be in the OEIS. These data do support a low-order polynomial growth, maybe $\Theta(n^2)$.

EDIT: It is now in the OEIS as sequence A275489.

Answer 2

If instead of common difference (2i+1) and varying x_i and hoping to cover 1 through m(n), you had common differences p_i for n distinct primes and all the x_i were 0, and you were just looking for the longest covered interval, you would bump into Jacobsthal's function (length of longest interval of consecutive nontotatives of m, in this case m being the product of the odd primes used).

Your problem is slightly more general, but you could use some existing data to inform your lower bound. I have a reading list and bibliography in an ArXiv print 1311.5944 : I recommend the papers by Hagedorn and (Hadju and Saradha), from which (just by choosing those progressions with prime arithmetic difference) you should achieve at least n log n growth.

Here is a quick way to get better than order n growth: Set x_i to 0 for those (2i+1) less than n which are prime. This leaves uncovered powers of 2, primes greater than n, and their products, using only n/log n of the progressions. Now use the remaining to cover the powers of two (so set x_i to 1, 2 , 4, ...) and as many primes and products larger than n until you run out. This will cover from 1 to about (n log n)/2 or better, because there aren't that many primes less than (n log n)/2 and the number does not get much bigger when you multiply those primes by small powers of 2. The theory predicts better than this, even when only prime difference arithmetic progressions are used.

Gerhard "All Publicity Is Good Publicity" Paseman, 2016.07.27.