Covering $\mathbb{N}$ with prime arithmetic progressions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T02:42:51Z http://mathoverflow.net/feeds/question/80494 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80494/covering-mathbbn-with-prime-arithmetic-progressions Covering $\mathbb{N}$ with prime arithmetic progressions asterios gantzounis 2011-11-09T15:51:48Z 2011-11-18T17:38:40Z <p>For every prime $p_i>2$ choose a $k_i\ge p_i$ , $k_i \in \mathbb{N}$ and take the arithmetic progression $A_i=k_i+np_i$ $n \ge 0$ . Is there any choice of the $k_i's$ such that $|\mathbb{N} \backslash \bigcup A_i | &lt; \infty$ ? </p> <p><strong>ADDED</strong> Does it makes any diferrence if we omit some other prime number (not 2)?</p> http://mathoverflow.net/questions/80494/covering-mathbbn-with-prime-arithmetic-progressions/80736#80736 Answer by Dimitris Koukoulopoulos for Covering $\mathbb{N}$ with prime arithmetic progressions Dimitris Koukoulopoulos 2011-11-12T07:01:39Z 2011-11-12T07:01:39Z <p>If you omit the condition that $k_i\ge p_i$, then here is an answer: for every integer $n$ there is some odd prime dividing $2n+1$. So choosing the $k_i$'s so that $2k_i+1\equiv0\pmod{p_i}$ provides a complete covering of the integers (by the congruence classes $\frac{p-1}2\pmod p,\;p>2$). Note that with the condition that $k_i\ge p_i$ this does not cover the numbers $(p-1)/2$.</p> http://mathoverflow.net/questions/80494/covering-mathbbn-with-prime-arithmetic-progressions/80859#80859 Answer by Aaron Meyerowitz for Covering $\mathbb{N}$ with prime arithmetic progressions Aaron Meyerowitz 2011-11-14T02:08:13Z 2011-11-17T08:53:35Z <p>I've completely changed my mind but I leave the old answer to explain the comments.</p> <p>It seems quite likely that there is a choice of residues which misses only the 40 integers </p> <p>$1, 2, 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 29, 30, 33, 36, 41, 44,51,$</p> <p>$53, 54, 56, 63, 65, 68, 69, 71, 75, 78, 81, 84, 86, 90, 93, 95, 96, 98, 99.$</p> <p>It arises from the following semi-greedy procedure:</p> <hr> <ol> <li><p>Only worry about integers starting with $s=100$ ($s=90$ is not enough).</p></li> <li><p>At each step, take the smallest integer $t \ge s$ not yet covered and attempt to cover it with the smallest unused odd prime $p$ such that $t+p$ is also not yet covered and $p \le t.$</p></li> <li><p>If there is no such prime then simply use the smallest unused prime (if it is less than $t$, otherwise, STOP!).</p></li> <li><p>Whatever prime is chosen, take the arithmetic progression $A=r+np$ for $n \ge 1$ where $t \bmod{p} =r$ </p></li> </ol> <hr> <p>So $1+3n$ knocks out $100,103,106,109,112,115,118,121\dots$ leaving $101$ next. Since $106$ is already covered we use $3+7n$ covering $101,108,122 \dots$ now $2+5n$ works for $102,107,117 \dots$ Next is $104$ and since $104+p$ is covered for $p=11,13,17$ we use $9+19n$.</p> <p>The residues chosen start out </p> <p>$[3, 1], [7, 3], [5, 2], [19, 9], [11, 6], [31, 17], [17, 9], [13, 9], [41, 32], [37, 8], [53, 14],$ </p> <p>$[43, 39], [67, 64], [61, 12], [23, 20], [79, 61], [89, 55], [103, 43], [47, 12], [29, 14]$</p> <p>Details: I followed this procedure using the $5132$ odd primes up to $49999.$ The number of unused primes less than $t$ (the first uncovered integer) starts at 24 when $t=100.$ It gets as low as 7 a few times, the last being when $t=1419.$ After $t=4925$ there are always at least $10$ unused primes below $t$ and from then on it seems to grow fairly steadily. After $t=33338$ there are (as far as I went) at least $500$ unused primes and after 4341 steps, $t=49980$ with $789$ unused primes available. I used up the remaining primes under $50{,}000$ (without checking if larger primes would be preferred by step 2) At step $5132$ the prime $43973$ was used for $t=60465.$ This left things with next target $t=60471$ and all $965$ primes $50000 \lt p \lt 60471$ as yet unused.</p> <p>Other starting values $s$ and the $t$ at which there is no available prime left are: </p> <p>$[10, 24], [20, 55], [30, 146], [40, 189], [50, 393], [60, 553], [70, 935], [80, 1969], [90, 4898].$</p> <p>A pure greedy strategy of starting at say $s=1000$ and always using the smallest unused odd prime seems to fail fairly quickly (perhaps in about $s$ steps.) The semi-greedy procedure stems from the idea that the main obstacle is the smallest uncovered integers.</p> <p>It may be better to not wait too long to use the smallest unused prime. Alternately, it might be better to look a little further in hopes of having $t$ along with two of $t+p,t+2p,t+3p$ all newly covered. </p> <p><strong>Old answer</strong> (this is left only to explain the comments)</p> <p>I'll mildly change the notation without changing the question. </p> <p>For every prime $p_i>p_0=2$ choose a residue $0 \le r_i\lt p_i$ and take the arithmetic progression $A_i=r_i+np_i$ $n \gt 0$ . Let $M=\mathbb{N} \backslash \bigcup A_i$ be the finite or infinite set of missed integers and $m_j$ be the $j$th member of $M$ (set $m_j=\infty$ if $M$ has less than $j$ elements). Once we have the residues up to $r_i$ we do know $M \cap \lbrace 1,2,\cdots,p_{i+1}-1 \rbrace$ and hence $m_j$ up to some point. So $m_0...m_5$ could be $1,2,4,8,16$ but only if we chose $r_1=0$ the first $5$ times. Otherwise we could have $1,2,4,m_4,m_5$ for $m_5 \le 13.$ If we take $r_1=1$ then can begin $1,2,3,6,9,12$ (the next choice is for $p_5=13$)</p> <p>The greedy procedure is to take $r_i=0$ and get $m_j=2^j.$ The choices $r_i=1$ gives $m_j=2^j+1.$ Gerry suggests taking $r_1=1$ and then making greedy choices. Up to $p_{30}=127$ this gives the $r$ values $1, 0, 1, 0, 1, 0, 2, 0, 3, 7, 2, 0, 4, 1, 1, 3, 2, 5, 3, 8, 4, 1, 0, 1, 0, 1, 1, 2, 1, 1$ and $m$ values $1, 2, 3, 6, 9, 12, 18, 24, 26, 42, 56, 86, 87, 93, 96, 117, 122, 126$ This does not even look like exponential growth (even if extended to $p_{96}=509$. It seems that $r_1=2$ followed by greedy choices might be a little better but still subexponential.</p> <p>I <em>made</em> the rash</p> <blockquote> <p><strong>claim:</strong> no matter how the $r_i$ are chosen, $m_j \le 2^j.$</p> </blockquote> <p><strong>NOTE:</strong> if my newer conjecture is true then for my chosen residues, $m_{40}=99$ but $m_{41}=\infty$</p> <p><em>I made</em> the even rasher claim below but Noam shut it down decisively. </p> <blockquote> <p><strong>claim:</strong> no matter how the $r_i$ are chosen, every integer interval $[x,2x-1]$ contains an $m$ value.</p> </blockquote> http://mathoverflow.net/questions/80494/covering-mathbbn-with-prime-arithmetic-progressions/81236#81236 Answer by Aaron Meyerowitz for Covering $\mathbb{N}$ with prime arithmetic progressions Aaron Meyerowitz 2011-11-18T08:51:21Z 2011-11-18T08:51:21Z <p>Here is a graph generated by the first 7500 steps of the method described above. At each stage it finds the smallest uncovered integer $m$ greater than 100 and covers it with a progression $r_i+np_i$ for $n\ge1.$ The last few primes chosen and corresponding $m$ covered are </p> <p>$[74099, 94245], [74297, 94263], [75329, 94281], [77893, 94283] [74903, 94296],$ $[77479, 94334], [77611, 94355], [77659, 94361], [74897, 94371], [77977, 94403]$</p> <p>At this stage the gap $m-p_i$ appears to be around $16500$ for $m \bmod{3}=1$ and $19500$ for $m \bmod{3}=2$</p> <p>The graph itself shows the number of unused odd primes $p \lt m$ at each stage. Starting after step 1000 or so it seems to increase pretty reliably at an average rate of slightly over $0.23$ for each step. </p> <p><img src="http://img528.imageshack.us/img528/5512/mograph.jpg" alt="alt text"></p> http://mathoverflow.net/questions/80494/covering-mathbbn-with-prime-arithmetic-progressions/81264#81264 Answer by Gerhard Paseman for Covering $\mathbb{N}$ with prime arithmetic progressions Gerhard Paseman 2011-11-18T16:48:45Z 2011-11-18T17:38:40Z <p>I like Aaron Meyerowitz's efforts and think his and similar methods deserve further study. I want to post my skepticism as a counter, and hope that something will arise from the contrast. I do not consider this post as being an acceptable answer though.</p> <p>The problem is essentially a shifted sieving problem. After taking the first $n$-many (finitely) primes $q_i$ with offsets $r_i$, one has an eventually periodic pattern of uncovered integers which repeats with period $Q_n = \prod_{i \leq n} q_i$, which contains $U_n = \prod_{i \leq n} (q_i - 1)$ uncovered numbers in each period, and has the first period starting somewhere near $M_n = \max_{i \leq n} r_i$. </p> <p>If the $q_i$ are the primes in ascending order, we have (Mertens) that $U_n$ is $O(Q_n/\log(q_n))$, which is (roughly) about $n$ times as many primes in the interval $(M, M + Q_n)$ when $n$ gets large, especially when $n$ is comparable to the largest integer $M$ allowed to be uncovered.</p> <p>If the distribution of coprimes to $Q_n$ were amenable to being nicely covered by arithmetic progressions of primes less than $q_n$, I might share Aaron's confidence. However, each later prime $q$ used is itself coprime to $Q_n$, and with small deviation will cover only about $1/q$ of what needs to be covered. I suspect that when $n$ gets to be about $Q_{24}/2$ using Aaron's sequence $Q_i$, he will run short on primes. It might be prudent to try more extensive simulations which leave no numbers greater than 50 uncovered.</p> <p>Gerhard "Saying As I Feel It" Paseman, 2011.11.18 </p>