mersenneforum.org (https://www.mersenneforum.org/index.php)
-   -   Triple prime search (https://www.mersenneforum.org/showthread.php?t=27317)

 hunson 2021-11-12 08:30

Triple prime search

Hi,

currently I am interested in triple primes. This is mainly because the record primes listed in Chris Caldwell's database are still quite small and therefore quick to check.
While choosing a 'n' to sieve, I asked myself whether there is a list or some coordinated prime search project for triple primes where one could check if the 'n' was already searched or up to which upper limit the exponent was searched.
I know that there are several similar projects / private range reservations etc. for other prime numbers.

If there is no such project, would it be of interest to create one?

regards

hunson

 firejuggler 2021-11-12 10:07

Look at [url]http://www.pzktupel.de/ktuplets.htm[/url]
4111286921397 * 2^66420 + d, d = -1, 1, 5 seeem to be the largest one know

 MattcAnderson 2021-11-12 10:50

There are some data at [URL="oeis.org"]oeis.org[/URL].
I did a search for 'prime triple' and received some results.
These are, of coarse, only the smallest few triples of each kind.

Also, there is some information in Wikipedia under[URL="https://en.wikipedia.org/wiki/Prime_k-tuple"] k-tuple[/URL].

Regards,
Matt

 hunson 2021-11-12 16:04

@firejuggler: The page you mentioned is about that what I thought about.

I image a project that summarizes the ranges that where tested with the count of primes, twins, triples, sieve depth etc. so that anyone who wants to search for triple primes can easily see whether the range that he choose was already worked on. Similar to the Carol-Kynea-Project ([url]https://www.mersenneforum.org/showthread.php?t=21216[/url]).

I have a chemistry background and me and some friends back in uni imagined how useful a journal would be that does not show the latest and greatest in organic chemistry, but the things not to try :) The title would be something like "Don't waste your time trying this ...".
So in that fashion one could image a summery of the ranges searched for triple primes. This would be especially interesting for "nice" exponents like k*2^55555, k*2^54321 or palindromic exponents etc. I am certainly not the only one that finds primes with these desirable. But since there is no public documentation about the sieving / checking efforts one could easily waste time on these if they were already checked up to a certain bound.

hunson

 Puzzle-Peter 2021-11-14 07:47

Hi hunson, welcome!

I do hold the current triple record. It's true, these numbers aren't really that big compared to twins or single primes records.

It's not my goal to discourage you from trying. These records are meant to be broken, after all. Still you need to be aware that finding a constellation of e.g. three primes is much harder than finding a single prime. But what really kept me from going higher is the fact that in a triplet there will always be one prime that can't be verified using LLR but will require a general prime proving software such as PRIMO. At 20.000+ digits you are looking at several months of computing on a powerful machine just to get that proof without knowing for sure it will be possible to prove it. There are limitations to the software that might make it impossible to prove a number prime even when it's smaller than PRIMOs current limit. Never had that happen to me though.

You could also try to find numbers of a special form so you can prove them thanks to knowing enough "helper primes" but that will slow down the sieving process. I'll be happy to point you in the right direction if you want to go this way. There's information and software available in this forum. I'll have to look for the right threads if you like.

TL;DR: I have considerable computing power and after doing trial runs & calculations I decided to not spend years trying to go higher. But that's just me. If you want to try, more power to you. Just be aware of the amount of work you're taking on. If you find enough people to help, it might be a fun project to run.

 hunson 2021-11-14 12:27

I do not shoot for a new record prime, I do not have the computing power for this. I am very pleased with a top 10, like with my twin-prime which was on the 9th place at the time. This is all just a fun project for me.
I am aware that I have to check the +5 form with PRIMO, that's mainly the reason why a ~12700 digit number is my goal. It should be still manageable to check this within a month or so on reasonable new hardware I guess.

The idea for a project page with an overview of the checked ranges/exponents might be still useful for someone who wants to find a prime in the top 15 like me!?

[QUOTE=Puzzle-Peter;593091]
You could also try to find numbers of a special form so you can prove them thanks to knowing enough "helper primes" but that will slow down the sieving process. I'll be happy to point you in the right direction if you want to go this way. There's information and software available in this forum. I'll have to look for the right threads if you like.
[/QUOTE]

Any help is very much appreciated! What forms do you suggest?

 henryzz 2021-11-15 08:46

[QUOTE=Puzzle-Peter;593091]Hi hunson, welcome!

I do hold the current triple record. It's true, these numbers aren't really that big compared to twins or single primes records.

It's not my goal to discourage you from trying. These records are meant to be broken, after all. Still you need to be aware that finding a constellation of e.g. three primes is much harder than finding a single prime. But what really kept me from going higher is the fact that in a triplet there will always be one prime that can't be verified using LLR but will require a general prime proving software such as PRIMO. At 20.000+ digits you are looking at several months of computing on a powerful machine just to get that proof without knowing for sure it will be possible to prove it. There are limitations to the software that might make it impossible to prove a number prime even when it's smaller than PRIMOs current limit. Never had that happen to me though.

You could also try to find numbers of a special form so you can prove them thanks to knowing enough "helper primes" but that will slow down the sieving process. I'll be happy to point you in the right direction if you want to go this way. There's information and software available in this forum. I'll have to look for the right threads if you like.

TL;DR: I have considerable computing power and after doing trial runs & calculations I decided to not spend years trying to go higher. But that's just me. If you want to try, more power to you. Just be aware of the amount of work you're taking on. If you find enough people to help, it might be a fun project to run.[/QUOTE]

Didn't you have a form that could be proved for all of -1/+1/+5 that could be sieved using polysieve?

 Puzzle-Peter 2021-11-15 12:29

[QUOTE=henryzz;593134]Didn't you have a form that could be proved for all of -1/+1/+5 that could be sieved using polysieve?[/QUOTE]

Yes, I just needed some time to hunt down the thread. It starts around here: [URL]https://mersenneforum.org/showthread.php?t=16705&page=8[/URL]

In short:
The idea was to start with a pair of precomputed twins. I'll call them s and s+2. These will be of the form k*b^n+d.

I then wanted to use the following formula for the candidates:
N=(s+2)*(a*s^2-3) + {-1, +1, +5} with "a" being the running variable.

N=a*s^3-3*s+2*a*s^2-6 Sorting into terms with and without "a":
N=(-6-3*s)+a*(2*s^2+s^3) + {-1, +1, +5}

N=(s+2)*(a*s^2-3)-1 can be tested using N+1 test and known prime factor s+2
N=(s+2)*(a*s^2-3)+1 can be tested using N-1 test and known prime factor s+2
N=(s+2)*(a*s^2-3)+5
=a*s^3-3*s+2*a*s^2-6 +5
= a*s^3-3*s+2*a*s^2-1 can be tested using N+1 test and known prime factor s
N=(s+2)*(a*s^2-3)+7
=a*s^3-3*s+2*a*s^2-6+7
= a*s^3-3*s+2*a*s^2+1 can be tested using N-1 test and known prime factor s which would give a quadruplet

So for triplets and quadruplets every number can be proven using one of the twin primes as a helper and the software PFGW. But how to do the sieving? I am a really bad programmer, but Robert Gerbicz was so nice and wrote his software "Polysieve"

Polysieve uses the form sorted into terms with and without "a" and calls them P(s) and a*Q(s) respectively. So for the example above we get
P(s)=-6-2*s and
Q(s)=3*s^2+s^3
Polysieve will ask for the degrees of P and Q, the coefficients and the "c" values (-1, +1, +5 in our example for a triplet, additionally +7 for quadruplet) and after sieving to your chosen limit will write a candidate file in ABC format that can be tested using PFGW.

There will probably be some questions left. Just ask, here or in PM. In case the "Germany" under your name means that German is your native language - so is mine. That might make the PMs a lot easier :smile:

 R. Gerbicz 2021-11-15 17:50

[QUOTE=henryzz;593134]Didn't you have a form that could be proved for all of -1/+1/+5 that could be sieved using polysieve?[/QUOTE]

Nice, not remembered for this, but for "large" n the k*2^n-1+1,+5 formula shouldn't be winning due to the slightly faster prp tests on special form?
You would need T(N)=O(log(N)^5/loglog(N)^2) bit operations (including sieve) to find a prp triplet near N=2^n, but for large N the cost of the "slow" primality test for the ugly k*2^n+5 number using elliptic curves (say with Primo) is still faster than T(N).

 Puzzle-Peter 2021-11-15 19:55

[QUOTE=R. Gerbicz;593172]Nice, not remembered for this, but for "large" n the k*2^n-1+1,+5 formula shouldn't be winning due to the slightly faster prp tests on special form?
You would need T(N)=O(log(N)^5/loglog(N)^2) bit operations (including sieve) to find a prp triplet near N=2^n, but for large N the cost of the "slow" primality test for the ugly k*2^n+5 number using elliptic curves (say with Primo) is still faster than T(N).[/QUOTE]

I'd never doubt your calculations. But the N ranges I am interested in are larger than the Primo limit. So "the polysieve way" is the only one I know to get large provable triplets or quadruplets.

 MattcAnderson 2021-11-25 04:20

Hi again all,

Here are two links that seem to be germane to this discussion.
Regarding 3 primes with the pattern (-1, 1, 5).

[URL="https://primes.utm.edu/glossary/xpage/PrimeTriple.html"]https://primes.utm.edu/glossary/xpage/PrimeTriple.html
[/URL]

[URL="http://www.pi-e.de/ktuplets.htm#largest3"]http://www.pi-e.de/ktuplets.htm#largest3
[/URL]

Also, the first few small ones are in OEIS.org at [URL="http://oeis.org/A007529"]A007529[/URL]

Hope that helps.
Regards,
Matt

 MattcAnderson 2021-11-27 15:00

I made a long-ish list of prime triple patterns or 3-tuples already in the database.

Some entries from The Online Encyclopedia of Integer Sequences

A022004 Initial members of prime triples (p, p+2, p+6).
5,11,17,41,101,107 and so on

A046134 p, p+2 and p+8 are primes.
3, 5, 11, 29, 59, 71, 101, 149, 191, 269 and so on

A046135 Primes p such that p+2 and p+12 are primes.
5, 11, 17, 29, 41, 59, 71, 101, 137, 179, 227, 239, 269, 281, 347, 419 and so on

A046136 Primes p such that p, p+4 and p+10 are primes.
3, 7, 13, 19, 37, 43, 79, 97, 103, 127, 163, 223, 229, 307, 349, 379, 439 and so on

A046137 Primes p such that p+4 and p+12 are also prime.
7, 19, 67, 97, 127, 229, 397, 487, 739, 757, 907, 1009 and so on

A046138 p, p+6 and p+8 are primes.
5, 11, 23, 53, 101, 131, 173, 191, 233, 263, 563, 593, 653 and so on

A046139 p, p+6 and p+10 are primes.
A046141 p, p+8 and p+12 are primes.

I have tried to contribute a few prime triples to OEIS but was told that these sequences are 'not of general interest'.
Maybe someone else would like to try.

Note the pattern Primes p such that p, p+2 and p+14 is not in the OEIS database.
It starts with 3,5,17,29,59,137,149,179,197,227,269,419,599,617,659,809,1019,1049,1277,1289,1607,1787,1997 and so on.

Any takers?

Regards,
Matt

 MattcAnderson 2021-11-27 17:01

triple prime log

Again,
If someone wants to put a few prime triples in OEIS, you can try.
I also tried (0, 2, 20) but that one was rejected too.
"not of general interest".
But I have made donations to OEIS and I received a holiday card from Neil Sloan himself, so the wheel may be greased.

Regards,
Matt

 MattcAnderson 2021-11-28 05:29

a short calculation

1 Attachment(s)
Now I have a calculation to share. It is a 3-tuple. Pattern is (0,2,18). I 'dialed it in' to fit on one piece of paper, and printed one. I used Maple computer algebra system and computer language.

I bet you can't calculate more :smile:

Look

Matt

Eddited to add - Have you ever dialed in a radio station? It is fun. Some of us know the joy of finding special numbers. You, dear reader, and I are special. We are elite. Some people can't even read. Best of luck. M

 MattcAnderson 2021-11-29 11:37

Triple prime search with pattern (0, 2, 20)

2 Attachment(s)
Where 20 is an arbitrary parameter :-)
This is what I was told by an OEIS.org referee. *sigh*

Hi again all,

Here are more triple prime search data. It is for
your enjoyment. I put it on this public forum so that
it may be shared. These are prime numbers p such that
p, p+2, and p+20 are all prime numbers.
So, this is a pattern of (0, 2, 20). And these are
the smallest such positive prime numbers. And all
prime numbers are positive integers.

Again, someone else can try to put this in OEIS.
Because, hey mankind needs to know this.
(But maybe, 'not of general interest')

Regards,
Matt

:mooc:

 kar_bon 2021-11-29 13:38

You could use PFGW with this script:
[code]
ABC2 \$a & \$a+2 & \$a+20
a: from 1 to 20000 step 2
[/code]

This will find all triples to n=20k within a minute!
The log file "pfgw-prime.log" will contain all pairs in this form:
[code]
3
3+2
3+20
- Complete Set -
[/code]

 Dr Sardonicus 2021-11-29 13:51

Just to make the list a bit more exclusive, I told Pari-GP to look for primes p such that p + 2 and p + 18 were the [i]next two consecutive primes[/i]. With the small limit I chose, it would have taken more time figuring out time saving refinements than it took to write and run a mindless script.
[code]k=0;forprime(p=3,35000,q=nextprime(p+1);r=nextprime(q+1);if(q-p==2&&r-q==16,k++;print(k" "p" "q" "r)))
1 1931 1933 1949
2 2111 2113 2129
3 2591 2593 2609
4 2801 2803 2819
5 3119 3121 3137
6 3371 3373 3389
7 3389 3391 3407
8 5021 5023 5039
9 5279 5281 5297
10 5879 5881 5897
11 6761 6763 6779
12 7331 7333 7349
13 9011 9013 9029
14 9239 9241 9257
15 10271 10273 10289
16 11351 11353 11369
17 11699 11701 11717
18 16631 16633 16649
19 17579 17581 17597
20 17789 17791 17807
21 18059 18061 18077
22 18311 18313 18329
23 18521 18523 18539
24 19139 19141 19157
25 20231 20233 20249
26 20771 20773 20789
27 22091 22093 22109
28 22619 22621 22637
29 24179 24181 24197
30 26861 26863 26879
31 27281 27283 27299
32 30011 30013 30029
33 31121 31123 31139
34 32141 32143 32159
35 32939 32941 32957
36 33809 33811 33827
37 34649 34651 34667
? [/code]

 Dr Sardonicus 2021-11-29 19:52

[QUOTE=MattcAnderson;594139]Where 20 is an arbitrary parameter :-)
This is what I was told by an OEIS.org referee.
<snip>[/QUOTE]In the spirit of "20 is an arbitrary parameter," the following mindless script looks for a triple p, p + 2, p + k which are [i]consecutive[/i] primes, for even integers k > 2 which are not congruent to 1 (mod 3). I ran the thing out to fifty million. The triples found may not be the least for the indicated k.

[code]? k=4;d=2;forprime(p=5,50000000,q=nextprime(p+1);r=nextprime(q+1);if(q-p==2&&r-q==k,print(k+2" "p" "q" "r);k+=d;d=6-d))
6 5 7 11
8 29 31 37
12 137 139 149
14 197 199 211
18 1931 1933 1949
20 4157 4159 4177
24 7127 7129 7151
26 12071 12073 12097
30 13337 13339 13367
32 13931 13933 13963
36 20441 20443 20477
38 28349 28351 28387
42 38459 38461 38501
44 58787 58789 58831
48 163061 163063 163109
50 172439 172441 172489
54 405089 405091 405143
56 439007 439009 439063
60 510617 510619 510677
62 667019 667021 667081
66 997811 997813 997877
68 1128821 1128823 1128889
72 1149059 1149061 1149131
74 1152419 1152421 1152493
78 1188071 1188073 1188149
80 1354391 1354393 1354471
84 1448219 1448221 1448303
86 1601867 1601869 1601953
90 3227039 3227041 3227129
92 4575377 4575379 4575469
96 4797071 4797073 4797167
98 4927931 4927933 4928029
102 5723897 5723899 5723999
104 8981459 8981461 8981563
108 12591041 12591043 12591149
110 13545797 13545799 13545907
114 15492437 15492439 15492551
116 15879047 15879049 15879163
120 16054277 16054279 16054397
122 18931697 18931699 18931819
126 36084311 36084313 36084437
128 43469651 43469653 43469779
?[/code]

For each k = 6*t + 2 or 6*t + 4 up to 150, these are k, and the [i]least[/i] triples p, p+2, p+k which are [i]consecutive[/i] primes. Note that p does not increase monotonically with k :smile:
[code]6 5 7 11
8 29 31 37
12 137 139 149
14 197 199 211
18 1931 1933 1949
20 521 523 541
24 1949 1951 1973
26 1667 1669 1693
30 2969 2971 2999
32 7757 7759 7789
36 12161 12163 12197
38 28349 28351 28387
42 20807 20809 20849
44 16139 16141 16183
48 163061 163063 163109
50 86627 86629 86677
54 25469 25471 25523
56 40637 40639 40693
60 79697 79699 79757
62 149627 149629 149689
66 625697 625699 625763
68 552401 552403 552469
72 173357 173359 173429
74 360089 360091 360163
78 716171 716173 716249
80 281429 281431 281509
84 265619 265621 265703
86 637937 637939 638023
90 544277 544279 544367
92 404849 404851 404941
96 1599707 1599709 1599803
98 1242641 1242643 1242739
102 838247 838249 838349
104 8981459 8981461 8981563
108 4297091 4297093 4297199
110 3593201 3593203 3593311
114 2637797 2637799 2637911
116 4131107 4131109 4131223
120 1349531 1349533 1349651
122 1895357 1895359 1895479
126 9707987 9707989 9708113
128 5825999 5826001 5826127
132 11188757 11188759 11188889
134 29980409 29980411 29980543
138 24947189 24947191 24947327
140 11501879 11501881 11502019
144 10343759 10343761 10343903
146 25507421 25507423 25507567
150 19918751 19918753 19918901[/code]

 MattcAnderson 2021-12-03 03:00

I appreciate all the typed comments you men.

 MattcAnderson 2021-12-05 14:51

more prime numbers - k tuples are more general than prime constellations

1 Attachment(s)
Wow!

Man, Norman Luhn from Germany (we are all residents of our earth)
I am impressed by all of your hard work.
Now I am an old man (but less than 50 years old :-)

My original calculations can be found at [URL="mattanderson.fun"]mattanderson.fun[/URL]

But my domain is only rented for another nine years (until 2030). I plan to re-rent the domain and
do more through my internet service provider. I use GoDaddy.com. I have not complaints about them,
but they are expensive - \$80 USD for two service calls. But worth it.

We are interested in k-tuples. Someone else might do more than me.
Regards,
Matt

 All times are UTC. The time now is 17:41.