Near repdigit primes on Numberphile

[Batalov]

Here is the latest sieve file (at p<10G with some primes skipped); it contains

   70466 Dec 13 12:15 sieve_9v89w_10G_inp70-100.txt
   44703 Dec 13 12:14 sieve_9v89w_10G_inp30-50.txt
 1014746 Dec 13 12:10 sieve_9v89w_10G.txt

The current density of survivors is ~14.7% (in the eariler posted 1M file it was ~16.7%)

I am running the 70000<=n<=10⁵ range.

[Batalov]

Here is the update on the bug:

> I later found that not only modulo Sophie Germain primes lead to a hang 
> but generally any argument whose order has large prime
> factors.

Hello Serge,

Thanks a lot for your bug report.

I know what is the problem but I do not know how to fix it yet.

We are using heuristic rules in the linear algebra part of the index calculus algorithm 
which fails for some primes.

The smaller the prime is, the higher the chance of failure 
(about 1% of failure for p ~ 2^28 and .5% for p ~ 2^30).
For order less than 2^27 we do not use index calculus, so the problem do not happen.

Cheers,
Bill A.

[lavalamp]

Originally Posted by lavalamp

Hm, just how small is it? I would expect it to get larger and larger as the primes increase.

Edit: If it really is quite a small fraction, then perhaps they could be added to an array and checked separately in a manner similar to my original sieve.

I decided to find out. I now have a 310 MB text file with all of the skipped potential factors in.

Between 270M and 1 billion, there are about 18.06 million primes we care about (+/-1 mod 10), and in that range there are 611,886 that are skipped (3.39%) in the updated sieve.

Between 1 and 10 billion, there are about 404.2 million primes we care about, and 24,424,494 are skipped (6.04%).

Between 9.9 and 10 billion, there are 2.17 million primes (we care about) and 338,646 are skipped (15.6%). Probably not worth going further at this time.

I would run the slower manual check on these numbers, but from the looks of the bug tracker a temporary patch will be implemented soon and it'll probably be quicker to wait on that.

[Batalov]

I heard from bug 1770 report that a patch was submitted into the stable tree; but that of course implies that an interested party has to build the new binary and/or wait for the nightly build (I think they had them?). ... Indeed.

I've sieved once again (on a different, faster machine, but before the patch) to 10G and the results matched. I've sieved up to 12G for kicks and giggles too (to make up for missed primes). I also sieved the 10²ⁿ⁺¹-10ⁿ-1 palindrome form to 10G, then produced ABC files for both and merged (for palindrome the cutoff previously was reported as 68k); I am testing the combined and size sorted set for 70-100k now and recently passed 80k. It is a little bit similar to the NeRDs last year project. I expect to find one prime or the other. At the very least they will be of interest to Kamada and E.W. (but not to the UTM site - too small).

EDIT: When the nightly build binary ( gp64-gmp-git06978b6.exe17-Dec-2015 04:27 8.3M ) had been posted, I have now started the no-guard-rails version of the sieve and so far it smoothly progressed to 0.6G which is of course good change; it appears that the bug is patched.

[lavalamp]

As opposed to double sieving in future, might I suggest simply storing the factors in an array? They can then be output to a file and checked after the fact.

I've attached some code for a sieve that does this, as well as a factor checker that can read in a sieve file and factors, strip any factors from the sieve and write out the result.

The sieve code also writes out a new sieve file at the end, but this could be commented out and left for the factor checker to perform.

The file formats are as follows, for the sieve:

{s = [
1,
0,
0,
0,
0,
1,
...
0,
0,
0
]}

And for the factors:

{f = [
1000151, 5729;
1000151, 505804;
1000171, 432916;
...
269903129, 427908;
269906869, 111107;
269953171, 183486
]}

There is nothing in the sieve file that gives an indication to the range. It is simply assumed to start at n=1. This could be fixed with the addition of a single variable, startn=xxx; but I have not done so. The sieve itself would then need to be modified slightly to take account of this.

Another pitfall of the sieve, it will remove primes! I had to manually add back in n=1. If/when the sieve progresses to 10^12, it will also remove n=6. This is only a minor nuisance at this point of course since we are well past checking these.

Another improvement that could be made is in the writing of output. Currently the code uses 1 write per n and per factor. This is very slow, and should probably be changed, but is good enough for now.

I have attached four files in a zip file:
sieve_270M.txt - a sieve file sieved up to 270M
sievecode.txt - updated code for sieving and recording factors
stripfactors.txt - code for verifying and removing factors from a sieve
transform.txt - code to transform the pari style sieve file into a list of candidates

[Batalov]

Well, from my perspective, it is as much a test for Pari as a test for primes, and 10G is way too deep for current searches anyway.
I do read the sieve file back, too, obviously, and because it is not prohibitively slow yet I have not thought about additional formats:

{
out="sieve_out_98989NGm10.txt";
lim=10^10; ns=10^6; pp=10^7;
s=vectorsmall(ns);
A=readvec("sieve_out_prev.txt");
for(i=1,#A,s[A[i]]=1);

forprime(p=10^10,lim, \\...

for(n=1,ns,if(s[n],write(out, 2*n)));
}

[Batalov]

Here is the file sieved to 10G with new, patched gp. 1804/1000000 additional candidates were removed (~1/82 of candidates from the earlier file; in particular, 28 from the interval 50k<=n<=70k)

[wombatman]

Quick update: currently at n=65140. Should be finished in a few days or so. No primes found as of yet.

[lavalamp]

Originally Posted by Batalov

10G is way too deep for current searches anyway.

Probably, but I like sieving. I get more of a kick from sieving and factoring than prime finding.

I've attached the sieve to 20 billion as cands_20G.zip, 141,255 candidates remain. I will be continuing on to 100 billion over the next 5-6 days, but the update on that might be a little delayed as I will be travelling around the time it finishes.

4234 additional candidates were removed in the 10-20 billion sieve range (nearly 3%), as well as 3 others I found while doing some performance testing of the upcoming range:

{f = [
40000853569, 419019;
95000786611, 255957;
100000007539, 25892
]}

I have also attached some updated scripts for factoring with Pari, as some of the previous code was untested and had bugs galore. These are now fixed and some other minor changes were made.

The files in A265383sieve.zip are:
sieve_20G.txt - a sieve file sieved up to 20 billion
sievecode.txt - code for sieving and recording factors
stripfactors.txt - code for verifying and removing factors from a sieve
transform.txt - code to transform the pari style sieve file into a list of candidates

Edit: I should mention that before running these scripts, you should allocate enough memory first, I typically do allocatemem(10^9), which should be more than enough (each instance running a sieve seems to use a little under 250 MB). For running the sieve I also do default(primelimit, 10^11), but sieving past 100 billion this will need to be higher.

[wombatman]

No primes between n=50k and 70k.

[MattcAnderson]

*grinz*