Path: csiph.com!news.mixmin.net!weretis.net!feeder1.news.weretis.net!news.solani.org!.POSTED!not-for-mail From: Thomas 'PointedEars' Lahn Newsgroups: comp.lang.javascript Subject: Re: Primality sieve challenge Date: Tue, 19 Jan 2016 19:59:12 +0100 Organization: PointedEars Software (PES) Lines: 36 Message-ID: <40372295.ejPoVfOnFb@PointedEars.de> References: <5b608a56-e16b-4467-a0ce-4e30f6796920@googlegroups.com> <37264925.IaaGi9xk8D@PointedEars.de> <87ziw27kln.fsf@bsb.me.uk> <2865358.ifOrN9Bpor@PointedEars.de> <0f34c52b-ae45-49b0-8363-080d3d11d5fb@googlegroups.com> <3532030.noGN7VB15C@PointedEars.de> <87bn8h64yr.fsf@bsb.me.uk> Reply-To: Thomas 'PointedEars' Lahn Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8Bit X-Trace: solani.org 1453229954 32120 eJwVyMkBwDAIA7CVSjDXOA3E+4+QVk+ZungH3BxGI8/UfjLBUghf5Gn9Yok0R4ZRsa3g/6PWBSaEERs= (19 Jan 2016 18:59:14 GMT) X-Complaints-To: abuse@news.solani.org NNTP-Posting-Date: Tue, 19 Jan 2016 18:59:14 +0000 (UTC) User-Agent: KNode/4.14.2 X-User-ID: eJwNxscBwDAIBLCVaEcZx9iw/wiJXoI6+w1zuGGxMrUTpXfqxFCZmA8pVEKl//KOtQE52yf5FipeP0qyyOoPSZwVHw== Cancel-Lock: sha1:vGP7lKqDgvXsfDWt/0jI5Ddh5r4= X-NNTP-Posting-Host: eJwNxskRwDAIBLCWuHYZlwMY919CopfgVE4GwcDDy9XXN/3KStJMcapafI3/TIZRBbbW5IHUBxnnEOc= Xref: csiph.com comp.lang.javascript:29355 Ben Bacarisse wrote: > Thomas 'PointedEars' Lahn writes: >> Scott Sauyet wrote: >>> Thomas 'PointedEars' Lahn wrote: >>>> Ben Bacarisse wrote: >>>>> but all those that have the form 6k + {0, 2, 3, 4} are clearly >>>>> composite. >>>> I can see why it is so for {0, 2, 4} (all multiples of 6 are divisible >>>> by 2, so are the sums when added 2 or 4), but why also for the summand >>>> 3? >>> Because 6k + 3 is divisible by 3. >> Why? I can see that it follows for k = 1 (9), k = 2 (15), k = 3 (21), >> and for several greater k, but why for *all* k? > > (6k + 3)/3 = 2k + 1 which is an integer. […] It is obvious to me, now that you have put it *this* way :) > The key is that every integer > 5 is in one of the six sets Rr = { 6k + > r | k ∈ N } where r is one of 0, 1,... 5. All the primes are there > somewhere in one or more of these sets. But all the numbers in R0, R2, > R3 and R4 are composite. What options are left? There may be no ^^^^^^^^^^^^^^^ > primes, of course, but if there are any, they must in either R1 or R5. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ And integers n = 6k − 1 (in your original statement) are members of the same equivalence class as integers m = 6k + 5. Thank you, I see it now. I missed the marked part as I misunderstood Gene’s statement so that it would mean that you can *find* primes that way. -- PointedEars FAQ: | SVN: Twitter: @PointedEars2 | ES Matrix: Please do not cc me. / Bitte keine Kopien per E-Mail.