Smallest $1\ 000$ digit number $x$ , such that $x$ , $x+2$ and $x+6$ are all prime?

Question

I am currently searching for the smallest $1\ 000$ digit number $x$, such hat $x,x+2,x+6$ are all prime (Such a triple is also called a prime constellation). For this, I wrote this PARI/GP - program :

? x=prod(j=1,10,prime(j));z=prod(j=1,3*10^4,prime(j));a=10^999-1;gef=0;while(gef
==0,a=a+2;if(gcd(a*(a+2)*(a+6),x)==1,if(gcd(a*(a+2)*(a+6),z)==1,if(ispseudoprime
(a,1)==1,print(a-10^999);if(ispseudoprime(a+2,1)==1,print(a);if(ispseudoprime(a+
6,1)==1,gef=1))))))

Since my computer is not the fastest, I only arrived at about $x=10^{999}+491\cdot 10^6$ and found no triple.

My strategy was

• Checking that $x(x+2)(x+6)$ has no prime factor upto $29$
• Checking that $x(x+2)(x+6)$ has no prime factor upto the $30\ 000$ th prime
• Checking the numbers $x$,$x+2$,$x+6$ one after another.

Can I further accelerate the program ? Maybe, there is a sieve method suitable for this task.

Of course, I invite everyone to run the task on another, perhaps more powerful software. I will continue my search, but it could be still a long way to find the smallest triple.

Answer 1

There are fast sieve methods for finding prime clusters. Generally these work with chunks of some primorial size, having built acceptable residues for the cluster. E.g. mod 30 there are only 2 possible values for starting a triple (0,2,6), only 8 mod 210, 64 mod 2310, etc. The larger the cluster, the fewer acceptable residues so the faster it works. Unfortunately with a triple we don't get nearly the benefit from this method as we do with larger clusters.

Charles has some ideas and Pari/GP code for triplets in this post on Mersenneforum.

I have some code in Perl/ntheory that does a decent job of finding clusters. I'm sure there is faster software, but I haven't found anything open source. Separately some researchers currently working on this area include Sorenson, Waldvogel, and Wroblewski. I've discussed ideas with Waldvogel and we seem to be doing basically the same thing, though it is hard to compare since their work, like the others, is closed source.

For your example, searching to 10^7 took 45 seconds with no solutions found. That's only 2x faster than your code. But there is also an example script that runs these in parallel, so on a fast machine we can get some linear speedup.

After about 2 hours it found 10^999 + 5537073001.

Answer 2

The most trivial of improvements is using the fact that $x$ (or $a$ in your program) must be $5$ modulo $6$ (it must be odd, and none of $x$, $x+2$, $x+6$ can be a multiple of $3$). So you can start $a$ at $10^{999}-5$ and increase it in steps of 6.

Sieving is also possible, and can replace the gcd calculations of your program. I suspect it will speed things up.
Simply set up an array of flags, representing the numbers $10^{999}$ to $10^{999}+n$. Then mark off all multiples of 2, all multiples of 3, all multiples of 5, ... all multiples of prime p, ... for however many primes you want to use. The numbers represented by the unmarked array entries are the remaining potential primes, so if you have $x$, $x+2$, $x+6$ unmarked you can primality-test them to see if they form a constellation.