Prime Constellations

[CRGreathouse]

That's the smallest known admissible constellation which could be used to disprove the conjecture, but probably not the smallest. So a reasonable goal for the present would be to find the smallest admissible constellation at every size below that one, so that the search for an instance would be easier. It's still pretty far out of reach to find the instance, but not so far out of reach to find the minimal constellation-counterexample.

[mart_r]

FYI, not long ago I had some fun with this 447-tuplet: With x =

5009951914481196036716104232575489030285584251044601342359020203825231451900652884390355382244744534611835647168564557449568664168936593509003877593703914635092162837455842866072080858730224487722204301970770553672020734651208336890384605394272355216495766895096493229307727133218196733788489413414116428402014140557155676084276892771440826081197750471158830948136395341005346088918917794851745670439411096000711391650249781564659934138878279701429080508198786950011218506501518798176197824729044533440885357134342476378402929397153185021

566009757*1327#+x+{0...3158} has no factors <= 1879 (well, except for the numbers with a factor <=113... you know what I mean :)

With x =

1388173992509816112803461248734756806731267311534137487095056189773828602569374727892219281742029185767647644253301700267504643337107321518512504084240248497746452160242024946950893090094263009500000085338999007067986124586724529373344444597643586404659832997581388897056816621539728097241109971488046693291951568251895134425510178719530713547036120145473243369970272454651421269126316597496697956034924474404949575278048139031848680398874728355382729754821975795670904110533742344594488460780426520629874194989408764092226417568188002252821333142779433260273322246559444715959431561724299841930446755260663885146210579059795594330302377912378682034689700722320883485926633376008520819945160145017809432258558568385797449002490228918391945485052043643801457540322412845789686532351371551525570389182970922876534466187458308692212019691798585152955321340630945034728719476684530270109947209791130718056533894046331991785944921343495413565121086179537501689418037178739653891203412741860331637497753089850216334727651955169929535192514884805237546031003217033560201468361978179856042292373751

528552216*3719#+x + {0...3158} has no factors <= 5309

I always consider it the "holy grail" of the prime tuplets.
Could anyone tell me if quantum computing could do the trick? Requirements (# of qubits etc.)?

BTW, is this search for patterns still on? Last update on Thomas Engelsma's site was 2009.

[Jens K Andersen]

Originally Posted by mart_r

566009757*1327#+x+{0...3158} has no factors <= 1879 (well, except for the numbers with a factor <=113... you know what I mean :)

It looks like you made a mistake somewhere. There are smaller factors for +6 and +1836:

x = 5009951914481196036716104232575489030285584251044601342359020203825231451900652884390355382244744534611835647168564557449568664168936593509003877593703914635092162837455842866072080858730224487722204301970770553672020734651208336890384605394272355216495766895096493229307727133218196733788489413414116428402014140557155676084276892771440826081197750471158830948136395341005346088918917794851745670439411096000711391650249781564659934138878279701429080508198786950011218506501518798176197824729044533440885357134342476378402929397153185021;
s = 566009757 * prod(n=1,primepi(1327),prime(n)) + x;
for(i=0,3158,forprime(p=2,1879,if((s+i)%p==0,\
  if(p<=113,next(2),print("+"i" gives factor "p)))));

+6 gives factor 1549
+1836 gives factor 1879

The smallest case for your form with no factor <= 1879 in the 447 numbers is
8106999318*1327#+x+{0...3158}
The smallest factor in that case is 1931 for +828.

Here is the smallest case for the form with no factor < 2011:
512345200137*1327#+x+{0...3158}
2011 is a factor for +1610

528552216*3719#+x + {0...3158} has no factors <= 5309

This also looks wrong.

x = 1388173992509816112803461248734756806731267311534137487095056189773828602569374727892219281742029185767647644253301700267504643337107321518512504084240248497746452160242024946950893090094263009500000085338999007067986124586724529373344444597643586404659832997581388897056816621539728097241109971488046693291951568251895134425510178719530713547036120145473243369970272454651421269126316597496697956034924474404949575278048139031848680398874728355382729754821975795670904110533742344594488460780426520629874194989408764092226417568188002252821333142779433260273322246559444715959431561724299841930446755260663885146210579059795594330302377912378682034689700722320883485926633376008520819945160145017809432258558568385797449002490228918391945485052043643801457540322412845789686532351371551525570389182970922876534466187458308692212019691798585152955321340630945034728719476684530270109947209791130718056533894046331991785944921343495413565121086179537501689418037178739653891203412741860331637497753089850216334727651955169929535192514884805237546031003217033560201468361978179856042292373751;
s = 528552216 * prod(n=1,primepi(3719),prime(n)) + x;
for(i=0,3158,forprime(p=2,5309,if((s+i)%p==0,\
  if(p<=113,next(2),print("+"i" gives factor "p)))));

+6 gives factor 3697
+272 gives factor 4937
+518 gives factor 5171
+576 gives factor 3253
+756 gives factor 2857
+926 gives factor 3457
+1068 gives factor 3931
+1166 gives factor 3499
+1290 gives factor 2593
+1290 gives factor 3511
+1296 gives factor 3631
+1418 gives factor 4049
+1470 gives factor 3709
+1610 gives factor 3533
+1632 gives factor 4397
+1656 gives factor 4783
+1712 gives factor 2711
+1712 gives factor 5039
+2022 gives factor 5059
+2108 gives factor 3491
+2450 gives factor 3527
+2562 gives factor 5297
+2928 gives factor 3583
+2970 gives factor 3967
+3050 gives factor 3797

+1290 and +1712 give two factors.
13 of the numbers have at least one factor below 3719 so they will never be prime and your form cannot give a 447-tuplet.


I did similar sieve work on a 592-tuplet in 2005: http://tech.groups.yahoo.com/group/p.../message/15948
At the time it was the smallest known candidate constellation to disprove the second Hardy–Littlewood conjecture.

[Jens K Andersen]

This gives no factor below 2111 for +1610:
2383611079554*1327#+x+{0...3158}
I stop here. It was just a small exercise in futility. If we actually tried to find a 447-tuplet then there are better but still utterly hopeless forms.

[mart_r]

Hmm... okay, I have to have a look at my numbers and code again.
Thanks for checking.

[MattcAnderson]

The trick to finding prime constellations is knowing where they are not.

All prime numbers greater than 2 are odd. Similarly, all primes greater than 3 have the form 1 or 5 mod 6. (Otherwise they would be divisible by 2 or 3) Also, the primes greater than 5 are in {1,7,11,13,17,19,23,29} mod 30.

I use the set of units mod n primorial to find constellations. For example, for the pattern [0,2,6] i know that the starting offsets must be {11, 17} mod 30. The code I use is

isprime(m*n+o+p)

m = multiplier (30)
n = number to search
o = offset (11,17)
p = pattern [0,2,6]

Because some of these variables are vectors, the isprime must be in a nested for loop.

This algorithm is implemented in the above java code. If anyone knows a better way to find constellations, I would love to hear it.

Regards,
Matt

[mart_r]

For my search for 13-/14-tuplets I used precalculated matrices for numbers m*67#+n*13#+{14849 or 15131}+{0,2,...,50} and looked in intervals of m=[1;2^31-1].

For every search interval m, candidates for n were selected where the whole pattern had no factor <= 67.
I used a single-integer matrix for factors 67<x<=69499 where a[x]=1 if a factor divided the pattern (i.e. if the last number of the pattern had a residue such that itself or one of the previous numbers were divisible, for instance if the residue is 50 then the first number has a factor) and a[x]=0 otherwise. So in the search for a possible number m I only had to take a look at a single value a[x] in every step of the trial division.
Additionally, for every search interval, I created a matrix that excluded m with factors 71, 73, 79, and 83 in the pattern (which roughly doubled my search speed, and trial division starts at x=89).
The primes were also stored in a matrix. When searching for small factors, which is the most time-consuming step here, no time should be wasted in trial dividing by numbers which are itself composite.
If no small factor was found, the pattern was checked for pseudoprimality (2^(p-1) mod p).

This method is efficient for large tuplets (and if the search interval m is big enough). I wouldn't recommend it for twins or triplets though.

[ktuple]

The search for super-dense patterns is currently on hold. The status is an interval that is over-packed by one prime must have a width in the range of 2529 < y <= 3159.

Larger widths can be over-packed with more primes, eg. a width of 41503 can hold 148 extra primes. A table of this over-packing is at http://www.opertech.com/primes/trophycase.html

Current work concerns this over-packing, a plot of the above table is at http://www.opertech.com/primes/trophy.bmp
Attempts are being made to prove this plot is truly concave up and never bends to the horizontal, meaning the plot is in the realm of combinatorics. The plot shown is 'known' values using todays computing power. The plot will rise faster as better packing algorithms are found.

Now the kicker, if the k-tuples conjecture is true, this plot must bend toward the horizontal, and reside in the world of logrithms.

Nice thing about conjectures is you can disagree with them even when they appear 100% sound. A conjecture is a conjecture until proven.

Tom

[MattcAnderson]

Although some of the people in this mathematical community do not appreciate this project, I have made another webpage regarding prime constelations, also called k-tuplets.

The Onlie Encyclopedia of Integer Sequences has refereed and accepted some of my work.

https://sites.google.com/site/primeconstellations/

Regards,

Matt C. Anderson

[CRGreathouse]

Originally Posted by MattcAnderson

Although some of the people in this mathematical community do not appreciate this project, I have made another webpage regarding prime constelations, also called k-tuplets.

I, for one, find it fascinating. I've meant to add the associated Hardy-Littlewood constants in comments to those sequences; I've written most of the code to do the calculations but lack for polishing.

And A008407 is fascinating. Any idea on how to prove bounds on its growth?

[science_man_88]

Originally Posted by CRGreathouse

I, for one, find it fascinating. I've meant to add the associated Hardy-Littlewood constants in comments to those sequences; I've written most of the code to do the calculations but lack for polishing.

And A008407 is fascinating. Any idea on how to prove bounds on its growth?

I looked at the sequence mentioned I can't find anything but going through links ( at least as far as I know) I got taken to: A118534 and noted that according to the twin prime conjecture: prime(n+1)-prime(n)=2 infinitely often that k was infinitely often prime(n)-2

PS: I just realized the obvious that under that same thought the least k should have 3 appearing infinitely often since 5 is 2 mod 3 and primes should be 5 mod 6 infinitely often.