Prime Constellations

[axn]

But LLR uses the "LLR" test for Woodall numbers, not a PRP test. So changing FermatBase isn't going to help here.

[Batalov]

I ran it on the certain 2¹⁰3ⁿ + 1, so the test wasn't LLR. It was the N-1 test.

[MattcAnderson]

I made another addition to the Online Encyclopedia of Integer Sequences. The list length went from 14 to 100.
http://oeis.org/A027570
The Maple Code is in the link. Now I am running another calculation for a second 10 tuple. Let me know if anyone can improve my code.

My code has a quick check for factors less than 100. It uses a greatest common divisor function just like Maple's isprime() command. All 10 potential primes in the constellation must pass the quick check before I waste time on a full isprime check.

Also, again, here is my summary page. It may contain errors. https://sites.google.com/site/primeconstellations/

Wish me luck.

Matt

[henryzz]

Try using polysieve2 http://mersenneforum.org/showthread.php?t=16705&page=8.
I am currently sieving that first tuple upto 1e16 with primes upto 1M. This will take 6 hours on a slow pc. The input string to polysieve2 is:
0 10 13 0 1 0 1 0 1 10 0 2 6 12 14 20 24 26 30 32 0 10000000 19 1000000 1000000 dec_0_10M.pfgw
The remaining candidates can then be run through pfgw after correcting the header line.

[MattcAnderson]

Hi Math People,

Thankys Henryzz. Your polysieve2 software is very useful for finding prime constellations. Currently, I am working on a 15 tuple pattern. Specifically, oeis.org/A257304 . This pattern has its largest prime 56 more than its smallest. Also, the prime pattern is
[0, 2, 6, 8, 12, 18, 20, 26, 30, 32, 36, 42, 48, 50, 56]

I assume the out22 file contains acceptable primes. But I am not sure.
There is some PARI code at http://oeis.org/A257137 that has a sorting function called isp.

Can anyone sort my out22.txt file for me.

Regards,
Matt

[danaj]

I added a prime cluster finder to my Perl module (although we care about the underlying C and C+GMP implementations). It is on github and will go in the next release. E.g. A213601:

perl -Mntheory=:all -E 'say join " ",sieve_prime_cluster(1,10**15, 6,10,12,16,22,24,30,34,36,40,42)'

where the cluster always starts with an implicit 0 and the list values must be even, increasing, and less than 2^31. Results all are all ES BPSW probable primes, so they are definite primes for 64-bit results.

It runs faster than polysieve2 for the A257304 and A027570 examples, as well as being easier to use. Of course polysieve2 does more than these linear clusters. It's hard to tell with only two reported times to compare, but it seems not too far off JKA's program. I also wrote a simple threaded front end.

I've been going through the OEIS entries. I truncated to 10k entries for 10-tuples and earlier, and am using a limit of 1e18 for 11-tuples, 1e19 for 12-tuples, and 1e20 for the 13-tuples. While the longer tuples are more efficient, they don't gain nearly enough to offset the increase in range, so they are taking much longer.

For the 15-tuple A257304 I estimate my Macbook would take about 1 day to replicate the existing results (up to 2e20), which I believe were done on Waldvogel's old cluster. Expanding to just 1e21 would be 5 days. Ugh. The 16-tuplets are worse -- they run 2x faster but the existing results go out 500x farther.

[MattcAnderson]

Hi Math People,

If there was a windows-64 executable program for the search for prime constellation numbers, I would be more than happy to run it on the computer here at home. I think this search project is ripe for new advances.

Regards,
Matt

[R.D. Silverman]

Originally Posted by MattcAnderson

Hi Math People,

If there was a windows-64 executable program for the search for prime constellation numbers,

What is a "prime constellation number"??? Please define.

I think this search project is ripe for new advances.

The same can be said for most technical subjects.........
What is special about this project that makes it ready for such?

[danaj]

At the risk of answering questions not directed to me,

Originally Posted by R.D. Silverman

What is a "prime constellation number"??? Please define.

I believe he means k-tuplets as used by Forbes: "For now, I will define a prime k-tuplet as a sequence of consecutive prime numbers such that the distance between the first and the last is in some sense as small as possible." Forbes gives a longer and less vague definition later.

The definitions of constellation, cluster, k-tuple, and k-tuplet are not used consistently. See also:
Prime Constellation on MathWorld
Prime constellations on OEISWiki (which makes a distinction between constellations/k-tuplets and clusters/k-tuples. where the former are maximally dense)

I think the OEISWiki page is well done, and makes a good distinction betweek a cluster (a strictly increasing set of k primes) and constellation (a maximally dense cluster).

Many people, including many well-known and active members of this forum, are finding large examples of these constellations. Matt and I (and Jörg Waldvogel and Jaroslaw Wroblewski and others) are looking at small examples, e.g. "the first N examples of n+(0,2,6,8,12,18,20,26,30,32,36,42,48,50,56) being prime"

[in response to "I think this search project is ripe for new advances."] The same can be said for most technical subjects.........
What is special about this project that makes it ready for such?

I think it is computationally interesting, but as far as I know there is no great mathematical reason. I would defer to what Waldvogel wrote in his reports (e.g. "Finding Clusters of Primes, II ; Progress Report 2006-2015"). There is some connection to the Hardy-Littlewood conjecture, but I don't really think this computation adds much.

What is interesting is that these sequences have been calculated and tabulated since at least the early 1980s (e.g. the 1982 Betsis and Säfholm results for k=14). Jens Kruse Andersen in 2006 or earlier, wrote a relatively simple program that calculates these very quickly. He used it to produce some results, but never released it. He did write a nice summary of the general method (that from reading forums and Wroblewski's AP26 paper seems to be the obvious solution). He teased us with it in mid-2012 on this thread (post 61).

I was bored during a plane flight to NY last month and wrote a cluster finder using similar methods to what he describes. For the examples I used, it was about half the speed of polysieve2. After more work, it is now faster than polysieve2, easier to use, a single step process, and there is a multi-threaded finder available. It's on Github with artistic license. It shouldn't be too long before it shows up as a Debian/Ubuntu/Fedora package and as part of Strawberry Perl for Windows. Of course polysieve2 finds other patterns, so they are not equal. From the two timing results available, JKA's program is still faster. I'm sure others could write something faster or improve my code, which could be rephrased "ripe for new advances."

I've been using it to expand the OEIS sequences. Some of these had previous times reported of "several weeks of computation time" with a reviewer comment of "I suspect the details of the computation may be worth a report or even a paper". The new computation is thousands of times faster (250x more range in under 1 day). I could see the method I use in my code in a detailed blog, or report, and certainly as a small part of a presentation, but I just don't see a paper. The general method was well known to specialists in the field 10 years ago.

[R.D. Silverman]

Originally Posted by danaj

At the risk of answering questions not directed to me,

Please do NOT answer such questions. I want to know what the OP meant, and not your interpretation.

If he meant k-tuplet, then why didn't he say "k-tuplet"??? Instead, he used terminology that I have not seen
before. It is fine if he wants to use his own terminology, but in order to communicate with others he must
define it.

I am well aware of existing literature.

I'd also like to see his reply as to why he believes this work is ready for new discoveries.....

[wblipp]

Originally Posted by R.D. Silverman

Please do NOT answer such questions. I want to know what the OP meant, and not your interpretation.

danaj,

Speaking for myself, please do continue answering when you have detailed information and intimate knowledge of the topic. I found your reply interesting. Bulletin Boards are naturally multi-way conversations, not dialogues. If the OP has anything more to add, especially as to why this work may be ready for new discoveries, I hope he will also respond.