Near repdigit primes on Numberphile

[wombatman]

Much obliged!

[Batalov]

Lavalamp is running a deeper sieve so if/when it will be available, you could replace the (rest of the) file later.
With the sieve, you can use -f0 of course (the sieve is already deeper than the default PFGW's singular pre-factoring, afaik).

[wombatman]

Yeah, I went ahead and used -f0. I'll see how many candidates are removed (and how far along I am).

[lavalamp]

Pari/gp is having issues in its znlog function sieving beyond 2^28, so here is a file that has been sieved to 270M, for all n <= 1M. That should keep PFGW going for a while.

[CRGreathouse]

Originally Posted by lavalamp

Pari/gp is having issues in its znlog function sieving beyond 2^28

Interesting, what happens?

[Batalov]

We've discussed it with LL by PM.
In a nutshell, znlog hangs for days at some point (soon after p>2^28).

Here is a debug case:

forprime(p=268890511,2^29,if(p%10!=1 && p%10!=9,next);q=sqrt(Mod(5,p));\
  o=znorder(t=Mod(10,p));r=znlog((1+q)/2,t,o);print1(p", "))
268890511, 268890521, 268890529, 268890551, 268890569, 268890599,
#--- and that's it

the order parameter can be dropped, it doesn't help. For this sieving we need order, anyway, so it is supplied, because it is claimed to be slightly faster.

P.S. I've just noticed that the hanging values of p are 2*q+1 with prime q:

forprime(p=268890511,2^29,if(p%10!=1 && p%10!=9,next);q=sqrt(Mod(5,p));\
  o=znorder(t=Mod(10,p));if(isprime(p\2),next);r=znlog((1+q)/2,t);print1(p", "))

runs fine

forprime(p=268890511,2^29,if(p%10!=1 &&  p%10!=9,next);q=sqrt(Mod(5,p));\
  o=znorder(t=Mod(10,p));if(!isprime(p\2),next);r=znlog((1+q)/2,t);print1(p",  "))

hangs immediately on the first value (p = 268890659 = 2*134445329+1)

[Batalov]

Incidentally, here is a faster version of the sieve from post "09 Dec 15 14:38".

If order is even and znlog exists, then znlog of the second root doesn't need to be evaluated -- their sum is o/2 or 3*o/2.
If order is odd, then sqrt(-1) doesn't exist and no more than one of the znlogs will exist.

{
out="sieve_out_30A.txt";
lim=1000000000;
ns=200000;
s=vector(ns,i,i=1);

forprime(p=19,lim,if(p%10!=1 && p%10!=9,next);q=sqrt(Mod(5,p));
  o=znorder(t=Mod(10,p));r=znlog((1+q)/2,t,o);if(r,forstep(n=r,ns,o,s[n]=0));
  if(o%2,if(r,,r=znlog((1-q)/2,t,o);if(r,forstep(n=r,ns,o,s[n]=0))),
     if(r,forstep(n=(3*o/2-r)%o,ns,o,s[n]=0))));

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

(This will be only useful of course after znlog bug is patched.)

[Batalov]

Here is an ugly sieve that will skip the SG primes, if you want to run it, lavalamp:

{
out="sieve_out_10Gn.txt";
lim=10^10; ns=10^6; pp=10^7;
s=vector(ns,i,i=1);

forprime(p=19,lim,if(p%10!=1 && p%10!=9,next);o=znorder(t=Mod(10,p));
  f=factor(o);if(f[#f[,1],1]>134217728,next);q=sqrt(Mod(5,p));
  r=znlog((1+q)/2,t,[o,f]);if(r,forstep(n=r,ns,o,s[n]=0));
  if(o%2,if(r,,r=znlog((1-q)/2,t,[o,f]);if(r,forstep(n=r,ns,o,s[n]=0))),
     if(r,forstep(n=(5*o/2-r)%o,ns,o,s[n]=0)));if(p>pp,pp+=10000000;print1(p" ")));

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

P.S. Submitted Bug#1770

[Batalov]

There were no primes for 10²ⁿ-10ⁿ-1, 30000<=n<=50000.

I will do 70000<=n<=10⁵ after the sieve to 10G is run.
(I am at 2.57G now; with the latest escapes of a small fraction of primes, the sieve runs really fast.)

[Batalov]

Found another (rather obscure) Pari/GP bug.

If you run more than one gp and both processes call e.g. factor() (as you can see my scripts do), then occasionally they collide in their tmpdir usage.

Symptom is this:

...
3160000009 3170000219 3180000007 3190000043 3200000087 3210000007 3220000051 3230000149 3240000011 3250000003 <-- these are "progress meter" printouts
  *** factor: Warning: I/O: can't remove file C:\CygWin\tmp\MPab/FREL.
  ***   at top-level: ...o=znorder(t=Mod(10,p));f=factor(o);if(f[#f[,1
  ***                                             ^--------------------
  *** factor: error opening output file [rename]: `C:\CygWin\tmp\MPab/FREL'.
  ***   Break loop: type 'break' to go back to GP prompt
break> p
3256357967

and even though this is shown as a warning - execution stops

[lavalamp]

Originally Posted by Batalov

with the latest escapes of a small fraction of primes

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.