Large Gaps >500,000

[danaj]

To update on windows in a command prompt:

cpan Math::Prime::Util::GMP
cpan Math::Prime::Util

Also, I just posted a crude sieve+PFGW script in another thread. At 8000 digits it came out about 6x faster than my next_prime, 26x faster than Pari/GP's nextprime, 84x faster than PFGW's nextprime. Some cleaning up and this could be useful here, especially with Robert's method of narrowing down the candidate multipliers, so we just need to call nextprime on a few numbers.

perl -Mntheory=:all -E 'use Math::GMP qw/:constant/; $n=10**8000; @f=Math::Prime::Util::GMP::sieve_primes($n+1,$n+500000,5e8); for (@f) { $i=$_-$n; die "PRP at n + $i\n" if !system("./pfgw64s -k -Cquiet -f0 -u0 -q\"10^8000+$i\"") && is_bpsw_prime($n+$i); } die "width too small";'

Things to improve include:
- the width and depth should be automatic.
- it should rerun another block instead of dying with low width (combine with previous).
- it should use a more efficient sieve call that has less overhead. I'm working on that now (it's a trivial issue at 8000 digits, important at 100k).
- perhaps clean up the PFGW display for each candidate.
- do something to tie together the Perl and PFGW 'n' values. Having it written twice is asking for something to get mismatched.
- as discussed, ideally this would be built in rather than system calls to the PFGW executable.
- there should be a prev_prime version. Shouldn't be a huge change.

If one does play with it, I will note:
- the width (500000 in above script) is a fairly minor performance concern. I'd make it 30 merits, then make sure we loop just in case we found a monster. Maybe it'd be better to only do 10-15 merits, but generally you want to only sieve once -- more width is pretty cheap compared to doing it a second time on the next block.
- depth (5e8 above) is trickier. 1e9 isn't a bad generic choice, but ideally we'd increase as the size went up. At first glance 1e12 seems too deep for 34k digits, but I haven't tested.

[robert44444uk]

Originally Posted by danaj

Also, I just posted a crude sieve+PFGW script in another thread. At 8000 digits it came out about 6x faster than my next_prime, 26x faster than Pari/GP's nextprime, 84x faster than PFGW's nextprime. Some cleaning up and this could be useful here, especially with Robert's method of narrowing down the candidate multipliers, so we just need to call nextprime on a few numbers.

perl -Mntheory=:all -E 'use Math::GMP qw/:constant/; $n=10**8000; @f=Math::Prime::Util::GMP::sieve_primes($n+1,$n+500000,5e8); for (@f) { $i=$_-$n; die "PRP at n + $i\n" if !system("./pfgw64s -k -Cquiet -f0 -u0 -q\"10^8000+$i\"") && is_bpsw_prime($n+$i); } die "width too small";'

Danaj

Does your code work on Windows - I am not good enough at Perl to know whether

if !system("./pfgw64s -k -Cquiet -f0 -u0 -q"10^8000+$i"")

is a command to bring in a windows version of pfgw or whether the "." is some other operating system.

What pfgw do you need to have?

BTW: Only one candidate in my 80021# set is over the 10 merit to date out of 4 tested, but everything was at least 6 merit. I'm testing 3 in parallel at 99991# and they have all cleared 400k gap size without finding either defining prime.

[danaj]

I don't normally use Windows for this stuff. The DOS command prompt is just so stupidly painful. If you do this inside a .pl file then you can avoid most of the issues.

This seems to work on my Windows machine:

perl -Mntheory=:all -E "use Math::GMP qw/:constant/; $n=10**1000; @f=Math::Prime::Util::GMP::sieve_primes($n+1,$n+500000,1e8); for (@f) { $i=$_-$n; die \"PRP at n + $i\n\" if !system(qq<pfgw64 -k -Cquiet -f0 -u0 -q\"10^^1000+$i\">) && is_bpsw_prime($n+$i); } die \"width too small\";"

You need to have pfgw64 in your path or in the current directory. If you haven't already, use "cpan Math::GMP" to get that module.

The system command calls whatever is inside it as a shell call. We look at the return code (which is inverted and shifted, but we just care whether it indicated success or not). You should see lots of lines like "10^1000+... is composite: ..." then a ".... is 3-PRP!" then a pause and "PRP at n + .." If you see things like "10 500 + 837 - Evaluator failed" then we're giving PFGW the wrong data. If you see "... is 3-PRP!" interspersed with the composite lines then we're probably giving PFGW the wrong data. The main issue seems to be the command prompt fiddling with things (e.g. a single caret or backslash caret gets eaten).

-f0 says don't do any trial factoring. -u0 says to not spend time doing console updates as we work on each candidate (with huge numbers maybe it'd be ok). -k -Cquiet tries to reduce it's per-candidate output.

[danaj]

Originally Posted by robert44444uk

Does your code work on Windows - I am not good enough at Perl to know whether
is a command to bring in a windows version of pfgw or whether the "." is some other operating system.

I was using 3.7.7 on my Linux machine, and "./pfgw64s" says to run the pfgw64s executable in my current directory. 3.7.10 on my Windows machine and I removed the ./ so it finds the first instance in the path (default for DOS seems to be to include current directory in PATH). I don't think there are any particular version requirements, other than the usual caveat that newer versions tend to have performance improvements.

[danaj]

Here is a nextprime.pl script that does auto width/depth. Run with something like perl nextprime.pl 10^^2000 or perl nextprime.pl "9257743*229#/4470 - 3228" (you need quotes if there are spaces in the expression, and the DOS command prompt requires repeated caret symbol that I don't believe Linux does). I've tested on Windows. For 10^12000 it is much slower than my Linux machine -- not sure how much is the computer (i7-4810MQ vs i7-6700K) and how much is Windows/Linux or something else.

#!/usr/bin/env perl
use warnings;
use strict;
use ntheory qw/:all/;
use Math::GMP;
$|=1;

my $pn = shift;
die "Usage:  nextprime.pl <n>, n is an expression\n" unless defined $pn;

my $n = $pn;
$n =~ s/\^/**/g;
$n =~ s/(\d+)#/primorial($1)/g;
$n =~ s/(\d+)/Math::GMP->new($1)/g;
#print "eval $n\n";
$n = eval($n) || die "Can't evaluate $pn";

my $width = int(length($n) * 2.3026 * 30);
my $depth = int(1e7 * length($n)/80);   # Not tuned
print "   width $width   depth $depth";

# In next release of ntheory, we will want to use sieve_range here
my @f = Math::Prime::Util::GMP::sieve_primes($n+1, $n+1+$width, $depth);

for (@f) {
  my $i = $_ - $n;
  #die "PRP at n + $i\n" if
  #  !system("pfgw64 -k -Cquiet -f0 -u0 -q\"$pn+$i\"")
  #  && is_bpsw_prime($n+$i);
  my $pfgw = `pfgw64 -k -Cquiet -f0 -u0 -q\"$pn+$i\"`;
  if ($pfgw =~ /is composite/) {
    print "$pn+$i composite";
  } elsif ($pfgw =~ /is \d+-PRP/) {
    die "PRP:  $pn + $i\n" if is_bpsw_prime($n+$i);
    print "$pn+$i is a 3-PRP but not prime";
  } else {
    die "Unknown PFGW output for $i:  $pfgw\n";
  }
}

die "width too small!";

Warning, this script does an eval on barely processed input -- do not use in any public-facing context until you address that.

[PawnProver44]

Sorry to bother, but are there any (known) gaps for the following?

1,000 digit primes: gap of approximately 25k

2,000 digit primes: gap of approximately 50k

3,000 digit primes: gap of approximately 100k

4,000 digit primes: gap of approximately 125k

5,000 digit primes: gap of approximately 150k

6,000 digit primes: gap of approximately 175k

7,000 digit primes: gap of approximately: 200k

8,000 digit primes: gap of approximately: 225k

Thanks to whoever knows. I am looking for a maximum point as to where I can guarantee there are primes in a certain range.

[danaj]

Wrong thread. Look for yourself at Nicely's site, in particular allgaps.dat. You won't get your guarantee from that though. Extremely likely != guarantee.

[robert44444uk]

Originally Posted by PawnProver44

Sorry to bother, but are there any (known) gaps for the following?

1,000 digit primes: gap of approximately 25k

2,000 digit primes: gap of approximately 50k

3,000 digit primes: gap of approximately 100k

4,000 digit primes: gap of approximately 125k

5,000 digit primes: gap of approximately 150k

6,000 digit primes: gap of approximately 175k

7,000 digit primes: gap of approximately: 200k

8,000 digit primes: gap of approximately: 225k

Thanks to whoever knows. I am looking for a maximum point as to where I can guarantee there are primes in a certain range.

allgaps.dat contains the smallest gap between primes that are a certain length - hence "allgaps" is incorrectly named, as there are known gaps of exactly any given gap size that are larger than the smallest gap listed in "allgaps".

Having said that, currently I would be fairly confident that all gaps over 250,000 that are in the allgaps.dat file are the only gaps that are known that are both of that size and have a merit of at least 10. This will change over time as more large gaps are found.

Your 8,000 digit primes demonstrating a gap of 225,000 have "merit" of about 12, for example

225052 C?P Jacobsen 2014 12.09 8083 17*18757#/30 - 117354

The list contains 687 gaps that are both > 225k in length bounded by primes of <8k digits. The top merit in that range is my own

418250 C?P RobSmith 2015 23.55 7713 11*17923#/46410 - 156344

[PawnProver44]

Thanks for link Robert44444uk, my computer crashed (due to server error) so I only got to see up to gaps of 6000.

[robert44444uk]

My strategy for large gaps has certainly paid off. From the first 20,000 A values in A*99991#/46410 as the midpoint I chose 5 with promisingly low remaining non-factored members in a range of 750 k either side of the midpoint, after a light sieve.

Of the 5 chosen, 4 have produced gaps >1,000,000, produced by a much heavier sieve and pfgw checking. All have merit >10. That is altogether 4 days on 4 cores for the two sieves and composite checking. The other chosen had a prp in the close to midpoint range so was quickly eliminated.

Given that the history of prime gap hunting has only produced 19 gaps of merit 10 which are over 1,000,000 in length, that is a massive pickup to 23 with no effort whatsoever!

And to top it off, all 4 gaps are, at the time of writing, undefined in length - 3 of them have one prp endpoint and one has no end prp points as yet. I'm sure that will change, but I am properly pleased with the result.

[robert44444uk]

And then there were three! One gap is now defined at 1,117,820.

One gap still has no end points and is a minimum of 1,132,828