mersenneforum.org Prime Constellations 2
 Register FAQ Search Today's Posts Mark Forums Read

2017-08-25, 21:59   #12
MattcAnderson

"Matthew Anderson"
Dec 2010
Oregon, USA

7·89 Posts

Hi Mersenneforum,

Here are a few more efforts regarding mathematical constellations.

These admissible constellations are not as close as possible to each other.

Regards,
Matt
Attached Files
 prime quads.pdf (143.7 KB, 87 views)

 2017-08-26, 20:14 #13 CRGreathouse     Aug 2006 173216 Posts You're looking for quadruples (p, p+2, p+6, p+14) of primes. Here's the way I would find these. Notice that p+4 must be a multiple of 3, so p, p+2, and p+6 must be consecutive primes. I can then loop through the primes (generated by a sieve), looking for instances of (p, p + 2, p + 6), and then check if p+14 is also prime. If so, I've found an example. This way I only need one primality test and no need to generate the n-th prime (which is slow). A better way would be to store two more primes and test if either one was p+14, avoiding the primality test entirely. (You couldn't fit two primes between p+7 and p+13 for congruence reasons.) But that's a bit more work. My simple code, in GP: Code: list(lim)=my(v=List(),p=5,q=7);forprime(r=11,nextprime(nextprime(lim\1+1)+1), if(q-p==2 && r-p==6 && isprime(p+14), listput(v,p)); p=q; q=r); Vec(v) This code can find all such primes p up to 10 million in a fraction of a second. The first prime is 5, the 10th is 3527, the 100th is 251057, the 1000th is 8191277, the 10000th is 181986587, the 100000th is 3358592177, and the millionth is 56147279387.
 2017-08-28, 16:14 #14 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×3×151 Posts Charles' Pari/GP code is more flexible, but Perl/ntheory has a cluster finder: Code: \$ perl -Mntheory=:all -E "say join ' ',sieve_prime_cluster(1, 10000, 2,6,14);" 5 17 227 1277 1607 1997 2237 2267 2657 3527 3917 4637 4787 6197 6827 8087 It builds a list of acceptible residues for a large (dynamic) primorial for whatever cluster you've given, then sieves to find a relatively small set of possible residues, followed by primality tests. This vastly cuts down on the number of tests and enables us to split the test as well (so we can just do the faster Euler-Plumb test on each offset, and only run Lucas tests if the whole cluster has passed the faster test). The more entries in the cluster the faster it gets (in terms of time per range). For this quadruple, it's about 34x faster than the simple Pari/GP script (albeit there are ways that Pari/GP could go faster). As alluded to a long time ago, there is an example script in the ntheory distribution that paralleliizes the search by the simple way of running N ranges at a time, collecting results. That's handy for some of the larger clusters, such as 14-tuplets (e.g. http://oeis.org/A257168). There are probably faster methods. Woldvogel and Jens Kruse Andersen have private tools for this, among others. I'm sure there are people on this forum who could write something faster if they desired.
2017-08-28, 17:12   #15
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by danaj The more entries in the cluster the faster it gets (in terms of time per range). For this quadruple, it's about 34x faster than the simple Pari/GP script (albeit there are ways that Pari/GP could go faster).
This approach is definitely better, and the factor will increase. Probably you could do it ~3x faster in gp with more care, and perhaps up to twice that fast directly in PARI, but it won't compete with purpose-built tools for sure.

2017-08-28, 23:07   #16
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts

Quote:
 Originally Posted by CRGreathouse This approach is definitely better, and the factor will increase. Probably you could do it ~3x faster in gp with more care, and perhaps up to twice that fast directly in PARI, but it won't compete with purpose-built tools for sure.
if only testing for the starting prime to be 17 mod 30 didn't add time/destroy to your code.

2017-08-29, 13:44   #17
CRGreathouse

Aug 2006

2×2,969 Posts

Quote:
 Originally Posted by science_man_88 if only testing for the starting prime to be 17 mod 30 didn't add time/destroy to your code.
Shouldn't be a big deal, the only number that could be divisible by 17 is p+14, but that will be tested for divisibility by 17 in the first step of isprime anyway. (If there were two numbers it would be a bigger deal, since it could avoid testing the first if the second had a small factor.)

Last fiddled with by CRGreathouse on 2017-08-29 at 13:45

2017-08-29, 14:12   #18
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by CRGreathouse Shouldn't be a big deal, the only number that could be divisible by 17 is p+14, but that will be tested for divisibility by 17 in the first step of isprime anyway. (If there were two numbers it would be a bigger deal, since it could avoid testing the first if the second had a small factor.)
it wasn't divisibility by 17 I was worrying about the original prime p in such a constellation can only be 17 mod 30 whenever it's greater than 5.

2017-08-29, 14:34   #19
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by science_man_88 it wasn't divisibility by 17 I was worrying about the original prime p in such a constellation can only be 17 mod 30 whenever it's greater than 5.
And where do you think that constraint comes from?

2017-08-29, 21:55   #20
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by CRGreathouse And where do you think that constraint comes from?
I looked at it in PARI/GP that's how I came to 17 mod 30 if p is 1 mod 5 ( 1,11, mod 30 after looking only at coprime remainders) then p+14 divides by 5 if p is 1 mod 3 (1,7,13,19 mod 30) then p+2 is divisible by 3. that leaves 17,23,29 mod 30 left. 29 can't have p+6 prime as it divides by 5. 23 can't have p+2 prime as it divides by 5. so 17 mod 30 is the only modular remainder mod 30 that can possibly give such a constellation.

2017-08-30, 02:45   #21
MattcAnderson

"Matthew Anderson"
Dec 2010
Oregon, USA

7×89 Posts

Hi Mersenne forum,

So I shine a light on some sets of 4 primes.
I do this because it is fun for me.

Have a look.
Regards,
Matt
Attached Files
 prime quad 2.pdf (96.7 KB, 111 views)

2017-09-14, 03:49   #22
MattcAnderson

"Matthew Anderson"
Dec 2010
Oregon, USA

11578 Posts

HI Mersenne Forum,

Here is a Maple worksheet that produces some sets of 3 primes.

Regards,
Matt
Attached Files
 3 prime b.pdf (120.3 KB, 82 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 MattcAnderson MattcAnderson 119 2018-03-14 20:22 CRGreathouse Software 10 2017-07-14 09:45 emily PrimeNet 3 2013-03-01 05:49 illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 13:36.

Thu Nov 26 13:36:00 UTC 2020 up 77 days, 10:46, 3 users, load averages: 1.44, 1.50, 1.53