Timeline for Covering $\mathbb{N}$ with prime arithmetic progressions
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 18, 2011 at 17:22 | vote | accept | CommunityBot | ||
| Nov 18, 2011 at 17:22 | history | bounty ended | Asterios Gkantzounis | ||
| Nov 18, 2011 at 16:57 | comment | added | Gerhard Paseman | I have just posted an answer which contains my guess. At this stage I cannot back it up with calculations, but I have started that process and perhaps others can finish. For your example, I think we won't see erosion before 10^15 is reached. The effect might be easier to see starting from 90, but it should be real telling starting from 50. I suspect even after O(10^5) trials using different starting moduli, the available primes will thin out before 10^8. Gerhard "Ask Me About System Design" Paseman, 2011.11.18 | |
| Nov 18, 2011 at 6:43 | comment | added | Aaron Meyerowitz | Gerhard, Maybe the algorithm could be tuned up but as it stands it avoids trouble starting at 100 but not at 90. What do you mean about small primes? Can you predict where the cushion of number of available primes less than the first uncovered integer (larger than 100) will start to erode? | |
| Nov 18, 2011 at 5:54 | comment | added | Gerhard Paseman | While it is a nice simulation, I suspect that one will not be able to continue it because of the scarcity of small primes. Indeed, I wonder why one needs to start at 100 instead of 50 for such an experiment. Gerhard "Hopes To Post Again Soon" Paseman, 2011.11.17 | |
| Nov 17, 2011 at 23:25 | comment | added | Aaron Meyerowitz | Asterois, I don't have any heuristic justification, although perhaps there is one. All I can say is that it works for the first 5000 primes ( up to 50,000) missing 40 integers under 100 and then working up steadily to a gap of nearly 1000 unused primes smaller than the first uncovered integer. And it is a fairly naive procedure. I did not expect that. | |
| Nov 17, 2011 at 21:46 | comment | added | Aaron Meyerowitz | Gerhard, I'm not sure it helps since I use the primes in a somewhat scrambled order $3, 7, 5, 19, 11, 31, 17, 13, 41, 37, 53, 43, 67, 61, 23, 79, 89, 103, 47, 29$. Define $J(p_i)$ to be the largest gap between numbers relatively prime to the first $i$ odd primes. Then $J(p_i)=p_{i-1}$ for primes $5,7,11,13,17,19$ So the 16 integers from $2394885$ to $2394900$ all have an odd divisor $19$ or smaller so $J(19)=17-1=16$. Going to the trusty OEIS oeis.org/A072752 (Maximum gap in one-stage prime-sieves) seems to say that the values continue $19, 22, 28, 32, 36, 44, 49, 52, 58$ | |
| Nov 17, 2011 at 18:13 | comment | added | Asterios Gkantzounis | i do not feel sure for your suggestions that such a cover works | |
| Nov 17, 2011 at 17:10 | comment | added | Gerhard Paseman | My suggested table uses 11 as ap(4), but using your example I should have 19 instead. Gerhard "Ask Me About System Design" Paseman , 2011.11.17 | |
| Nov 17, 2011 at 17:04 | comment | added | Gerhard Paseman | Your cover provides a lower bound for certain j(m) where m is the product of some odd primes up to some N. If you can give me an idea as to the growth rate from your procedure, I might be able to determine its feasibility. Let a(n) be the length covered after using the nth prime ap(n). Can you provide the table for me for n up to 50? I imagine it starts (3,1),(7,2),(5,4),(11,5 or 6). To be clear, the second component is a(n) and is not always the length of the longest interval covered, but is related to the next uncovered integer. Gerhard "Ask Me About System Design" Paseman, 2011.11.17 | |
| Nov 17, 2011 at 15:49 | comment | added | Aaron Meyerowitz | An interesting note: starting with $s=100$ there were $114$ times that I was unable to knock out $t,t+p$ at the same time. But starting with $s=1000$ that never happened. So it seems likely that the evolving pattern of covered and uncovered above $s$ is invariant as long as $s$ is large enough. | |
| Nov 17, 2011 at 8:53 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 538 characters in body
|
| Nov 17, 2011 at 7:53 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
total rewrite
|
| Nov 15, 2011 at 19:27 | comment | added | Gerhard Paseman | Westzynthius is good if you pick one target in advance and say I will fill that target interval with small primes. It looks to me like you are asking to pick successively larger targets to the cover with small and medium primes; I don't know enough about the distribution to say that you can hit all the targets with the mild constraints you impose. I suspect that it will fail for a reason like not covering the powers of 2 "fast enough". However, I don't know what "fast enough" is. Gerhard "Not Trying To Be Crazy-making" Paseman, 2011.11.15 | |
| Nov 15, 2011 at 6:34 | comment | added | Asterios Gkantzounis | @Gerhard Paseman: Gerhard,Your opinion about the last comment??? | |
| Nov 15, 2011 at 6:33 | comment | added | Asterios Gkantzounis | Westzynthious article admits that you can have "big" intervals without using many primes. This could be a problem for claims for large numbers but i am not sure , i am working on it.... mathoverflow.net/questions/37679/… | |
| Nov 14, 2011 at 20:36 | history | edited | Kevin O'Bryant | CC BY-SA 3.0 |
changed p_96 to p_{96}
|
| Nov 14, 2011 at 6:52 | comment | added | Gerhard Paseman | I'm not sure if I understand the first claim, but I suspect that it would follow from a result of Kanold (j(m) <= 2^n) on Jacobsthal's function. The problem solution would follow if we could show that the repeating pattern above can't be covered by a.p.'s slowly enough, i.e. that r_j <= p_j for a prime p_j with M < p_j < prod. Of course, if I could convince myself of that, I would be writing this in an answer box instead of here. Gerhard "Ask Me About System Design" Paseman, 2011.11.13 | |
| Nov 14, 2011 at 6:44 | comment | added | Gerhard Paseman | If one lets M be an upper bound to the missed integers, and lets r_i (without loss of generality) satisfy p_i <= r_i < 2p_i, then one has an interval of length M of some missed integers followed by (after adding the progressions using all the allowed primes below M) a repeating pattern of period O(4^M) which contains few missed numbers, and the r_i can be chosen to acheive covering numbers in (M,M+j(prod)) where prod is the product of the primes less than M. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2011.11.13 | |
| Nov 14, 2011 at 4:33 | comment | added | Noam D. Elkies | And thus knocks out $[8,20]$, since we can use $17$ and $19$ to cover $18$ and $19$ respectively, and $20$ is covered already. [I deleted tmy follow-up comment that claimed the same residues also cover $1,2,5$, because that requires that some $r_i < p_i$.] | |
| Nov 14, 2011 at 4:08 | comment | added | Aaron Meyerowitz | that's nice, it even knocks out [8,17] | |
| Nov 14, 2011 at 3:56 | comment | added | Noam D. Elkies | Counterexample to the final claim: $x = 8$ and $$ \begin{array}{c|ccccc} p_i & 3 & 5 & 7 & 11 & 13 \\ \hline r_i & 8 & 10 & 9 & 12 & 13 \end{array} $$ | |
| Nov 14, 2011 at 3:02 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 210 characters in body
|
| Nov 14, 2011 at 2:08 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |