5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the calculation, I think I just need a faster computer :) $\endgroup$ – Peter Feb 20 at 21:40
  • $\begingroup$ I needed 2-3 days with my code and my computer to arrive at $5\cdot 10^8$ , so I think a reason is also that PARI/GP is not so fast. $\endgroup$ – Peter Feb 20 at 21:42
  • $\begingroup$ For this example, a faster computer is a lot of it. Slightly faster code plus running in parallel. When looking for things like prime octuplets then the residue method is far more advantageous. $\endgroup$ – DanaJ Feb 20 at 21:43
  • $\begingroup$ Which software can you suggest ? Perl ? $\endgroup$ – Peter Feb 20 at 21:44
  • $\begingroup$ You could write something in Pari, or use the C / C+GMP code from the Perl module, or use Perl with the module. The latter is easiest if you just want to search for clusters, especially with the threads example to speed things up. Eventually I'll put it all in a plain C module and write a Python wrapper (and perhaps other languages). $\endgroup$ – DanaJ Feb 20 at 22:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.