Prime Constellations 2

[MattcAnderson]

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

[CRGreathouse]

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:

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.

[danaj]

Charles' Pari/GP code is more flexible, but Perl/ntheory has a cluster finder:

$ 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.

[CRGreathouse]

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.

[science_man_88]

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.

[CRGreathouse]

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.)

[science_man_88]

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.

[CRGreathouse]

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?

[science_man_88]

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.

[MattcAnderson]

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

[MattcAnderson]

HI Mersenne Forum,


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


Regards,
Matt