mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Information & Answers (https://www.mersenneforum.org/forumdisplay.php?f=38)
-   -   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



Also look at this thread [url]https://www.mersenneforum.org/showthread.php?t=16705&highlight=tuple[/url]

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

Thanks for the answers.


@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

Thanks for your input Puzzle-Peter.
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


All times are UTC. The time now is 16:16.

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