# Covering a finite subset of $\mathbb{N}$ with prime arithmetic progressions

Because of a problem I ran into I am trying to get a quick start in covering with arithmetic progressions.

First I want to say I am aware of this previously asked question: Covering $\mathbb{N}$ with prime arithmetic progressions

Similarly to what is asked there I am interested in covering with arithmetic progressions of the type $A_{i}=k_{i}+np_{i}$ where $p_{i}$ is prime, $k_{i} \in \mathbb{N}$ and $n \in \mathbb{N_{0}}$.

Differently, my interests are however in covering of finite sets of the type $\{1, 2, \ldots, N\} \subset \mathbb{N}$ where $k_{i}<p_{i}$ and $p_{1} \leq p_{i} \leq p_{m}$.

By checking out some numbers it looks like that if all $k_{i}=p_{i}-1$ the covered set is $\{1, 2, \ldots, p_{m+1}-2 \}$.

So my questions are:

Let $p_{1} \leq p_{i} \leq p_{m}$ be the first $m$ consecutive primes and $\forall p_{i}$ let $A_{i}=k_{i}+np_{i}$ be $m$ arithmetic progressions, where $n \in \mathbb{N_{0}}$ and $k_{i} \in \mathbb{N}$ such that $1 \leq k_{i}<p_{i}$. Obviously is the arithmetic progression $A_{1}=k_{1}+np_{1}=1+2n$ fixed and covers all the odd numbers in all considerations.

1. If $\forall p_{i}$ with $k_{i}=p_{i}-1$ is the covered set always $\{1, 2, \ldots, p_{m+1}-2 \}$, that is are all numbers up to $N=p_{m+1}-2$ covered?
2. Will all sets of $k_{i}$ values where one or more $k_{i}<p_{i}-1$ give less coverage?
3. (If "no" to 2.) Is there any set of $k_{i}$ values where one or more $k_{i}<p_{i}-1$ gives more coverage, that is covers numbers up to $N>p_{m+1}-2$?

Additional questions/help. I would appreciate all relevant information possible, like: Has this been proved?, Then by whom?; Any textbooks discussing this or very similar kind of problems; Websites; etc.

• I'd suggest to make this question self-contained (while it should mention the respective previous OM Question, let your new question explain each term independently, to avoid any confusion). – Włodzimierz Holsztyński Sep 11 '14 at 3:12
• You wrote: I am interesting. It is great that you are interesting but you can ask way more SPECIFIC questions than just claiming than you are interesting (of course I believe that you are). – Włodzimierz Holsztyński Sep 11 '14 at 3:20
• Given any $r$, let $p$ be a prime dividing $r+1$, then $r$ is in the arithmetic progression $(p-1)+np$. – Gerry Myerson Sep 11 '14 at 3:26
• I have updated the question in an attempt to make it more self-contained (and correct grammar). I hope I have understood your suggestions Wlodzimierz. Your input Gerry is very helpful, it gives a "quick start" insight. Thanks to you both. – augu Sep 11 '14 at 4:00
• @Gerry Myerson as I said it was a good "quick start insight" giving me something to think about. Having done that I understand as all numbers up to $p_{m+1}$ are divisible by one or more prime up to $p_{m}$ your suggestion shows that the numbers are covered with this kind of arithmetic progressions. Thanks again. – augu Sep 11 '14 at 22:20

## 1 Answer

This is equivalent to studying large intervals of numbers that are not coprime to a product of some selected prime numbers. When one has such a large interval, one can translate it by subtraction to begin at 1, and can compute the requisite k_i. Taking m to be 5, n the product of the first m primes, in this case n=2310, we find the interval of nontotients of n from 114 to 126: translating the k's in increasing order of p_i are 1,1,2,6,8. This tiles 13 integers, and 13 is greater than 13-2.

Again searching MathOverflow for Jacobsthal's function should give you more examples

• Aha! Somehow your previous Jacobsthal reference missed my attention. Not that I understand it immediately, but I have confirmed that your $k$ values $1,1,2,6,8$ give better coverage indeed. This confirms the answer to question 2. is "no" and 3 is "yes". Thanks a lot. – augu Sep 12 '14 at 20:59
• Unfortunately I don't have enough reputation to vote up your answer. – augu Sep 12 '14 at 21:00