mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > MattcAnderson

Reply
 
Thread Tools
Old 2017-08-25, 21:59   #12
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

10010101002 Posts
Default

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
File Type: pdf prime quads.pdf (143.7 KB, 61 views)
MattcAnderson is offline   Reply With Quote
Old 2017-08-26, 20:14   #13
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×7×419 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-08-28, 16:14   #14
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2017-08-28, 17:12   #15
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16EA16 Posts
Default

Quote:
Originally Posted by danaj View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-08-28, 23:07   #16
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-08-29, 13:44   #17
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16EA16 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
CRGreathouse is offline   Reply With Quote
Old 2017-08-29, 14:12   #18
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-08-29, 14:34   #19
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×7×419 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2017-08-29, 21:55   #20
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-08-30, 02:45   #21
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

22×149 Posts
Default

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
File Type: pdf prime quad 2.pdf (96.7 KB, 80 views)
MattcAnderson is offline   Reply With Quote
Old 2017-09-14, 03:49   #22
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

22·149 Posts
Default

HI Mersenne Forum,


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


Regards,
Matt
Attached Files
File Type: pdf 3 prime b.pdf (120.3 KB, 54 views)
MattcAnderson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime Constellations MattcAnderson MattcAnderson 119 2018-03-14 20:22
Prime constellations? CRGreathouse Software 10 2017-07-14 09:45
NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 561 2013-03-29 16:55
disk died, prime work lost forever? where to put prime? on SSD or HDD? emily PrimeNet 3 2013-03-01 05:49
The 40th known Mersenne prime, 220996011-1 is not PRIME! illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 01:15.

Tue Aug 11 01:15:01 UTC 2020 up 24 days, 21:01, 1 user, load averages: 1.66, 1.53, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.