mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2021-11-12, 08:30   #1
hunson
 
Feb 2020
Germany

418 Posts
Default 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
hunson is offline   Reply With Quote
Old 2021-11-12, 10:07   #2
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

22·11·61 Posts
Default

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



Also look at this thread https://www.mersenneforum.org/showth...ighlight=tuple
firejuggler is offline   Reply With Quote
Old 2021-11-12, 10:50   #3
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

3C516 Posts
Default

There are some data at oeis.org.
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 k-tuple.

Regards,
Matt
MattcAnderson is online now   Reply With Quote
Old 2021-11-12, 16:04   #4
hunson
 
Feb 2020
Germany

3×11 Posts
Default

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 (https://www.mersenneforum.org/showthread.php?t=21216).

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
hunson is offline   Reply With Quote
Old 2021-11-14, 07:47   #5
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·173 Posts
Default

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.
Puzzle-Peter is offline   Reply With Quote
Old 2021-11-14, 12:27   #6
hunson
 
Feb 2020
Germany

1000012 Posts
Default

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:
Originally Posted by Puzzle-Peter View Post
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.
Any help is very much appreciated! What forms do you suggest?

Last fiddled with by hunson on 2021-11-14 at 12:28
hunson is offline   Reply With Quote
Old 2021-11-15, 08:46   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,969 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
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.
Didn't you have a form that could be proved for all of -1/+1/+5 that could be sieved using polysieve?
henryzz is offline   Reply With Quote
Old 2021-11-15, 12:29   #8
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·173 Posts
Default

Quote:
Originally Posted by henryzz View Post
Didn't you have a form that could be proved for all of -1/+1/+5 that could be sieved using polysieve?

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


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

Last fiddled with by Puzzle-Peter on 2021-11-15 at 12:34
Puzzle-Peter is offline   Reply With Quote
Old 2021-11-15, 17:50   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

72×31 Posts
Default

Quote:
Originally Posted by henryzz View Post
Didn't you have a form that could be proved for all of -1/+1/+5 that could be sieved using polysieve?
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).

Last fiddled with by R. Gerbicz on 2021-11-15 at 17:55 Reason: renamed variables
R. Gerbicz is offline   Reply With Quote
Old 2021-11-15, 19:55   #10
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·173 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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).
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.
Puzzle-Peter is offline   Reply With Quote
Old 2021-11-25, 04:20   #11
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

5·193 Posts
Default

Hi again all,

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

https://primes.utm.edu/glossary/xpage/PrimeTriple.html


http://www.pi-e.de/ktuplets.htm#largest3


Also, the first few small ones are in OEIS.org at A007529

Hope that helps.
Regards,
Matt

Last fiddled with by MattcAnderson on 2021-11-25 at 04:26 Reason: add third link
MattcAnderson is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Twin prime search? MooooMoo Twin Prime Search 115 2010-08-29 17:38
Exponential prime search Citrix Prime Sierpinski Project 37 2009-08-17 06:32
Benson's prime search Kosmaj Riesel Prime Search 67 2009-01-18 21:59
Prime Search on PS-3? Kosmaj Riesel Prime Search 6 2006-11-21 15:19
Prime Search forum geoff Forum Feedback 3 2006-07-26 03:17

All times are UTC. The time now is 04:56.


Sun Dec 5 04:56:52 UTC 2021 up 134 days, 23:25, 0 users, load averages: 1.33, 1.51, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.