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.

  • $\begingroup$ 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). $\endgroup$ Sep 11 '14 at 3:12
  • $\begingroup$ 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). $\endgroup$ Sep 11 '14 at 3:20
  • $\begingroup$ Given any $r$, let $p$ be a prime dividing $r+1$, then $r$ is in the arithmetic progression $(p-1)+np$. $\endgroup$ Sep 11 '14 at 3:26
  • $\begingroup$ 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. $\endgroup$
    – augu
    Sep 11 '14 at 4:00
  • 1
    $\begingroup$ @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. $\endgroup$
    – augu
    Sep 11 '14 at 22:20

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

  • $\begingroup$ 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. $\endgroup$
    – augu
    Sep 12 '14 at 20:59
  • $\begingroup$ Unfortunately I don't have enough reputation to vote up your answer. $\endgroup$
    – augu
    Sep 12 '14 at 21:00

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.