Near repdigit primes on Numberphile

[science_man_88]

Originally Posted by CRGreathouse

I think Mini-Geek was talking about sieving much higher than 7.

he asked how not how high, or was it potentially obvious.

[wombatman]

No primes for n=20k to 21k.

[wombatman]

Based on how fast everything's going, I'll go ahead and run up to n=30k if that's alright.

[Batalov]

Originally Posted by Mini-Geek

How did you pre-sieve this sequence? Is there a tool out there that can take this form, or is it easy to tweak some siever to take a general-form number, maybe? I just ran PFGW with -f so it tried factoring each number before doing its N+1 test.

Don't run N+1 test, run -f and a simple PRP test - you may save a ton of time. Don't run LLR in "ABC \$a^\$b-\$a^\$c-1" mode either because if fails to report primes (I posted about that in the LLR thread).

The sieve I used was written quick'n'dirty in Pari.
I vaguely remember that there was some sieve for this form, too. Ksieve if I am not mistaken.

[lavalamp]

I was unable to find Ksieve, do you know who wrote it or where there's a download for it?

Until a better alternative arrives, I've attached a list of n for 10^2n - 10^n - 1 for n <= 100,000 and it has been sieved for p < 1,000,000.

Here is the code in pari/gp for anyone who wants to check for correctness or edit it to sieve deeper.

{

out="C:/sieve_out.txt";

lim=1000000;
ns=100000;

s=vector(ns,i,i=1);

forprime(p=2,lim,
t = Mod(10,p);
for(n=2,ns,

t*=10;

if(t*(t-1)==1,s[n]=0)

)
);

for(n=1,ns,

if(s[n]==1,write(out, n))

);

}

[Batalov]

Originally Posted by lavalamp

Here is the code in pari/gp for anyone who wants to check for correctness or edit it to sieve deeper.

It is correct.

Ksieve was Phil Carmody's. Someone picked it up for the 10^a-10^b-1 searches that were run about a year ago...
I tried it myself (iirc for a very brief time) but didn't figure the magic that effects the 'abc10' sieve mode.

[Batalov]

Here's a somewhat faster sieve:

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

forprime(p=11,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));
r=znlog((1-q)/2,t,o);if(r,forstep(n=r,ns,o,s[n]=0)));

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

[science_man_88]

Originally Posted by Batalov

Here's a somewhat faster sieve:
...

is it any faster in parallel with say parforprime or parfor ? those forstep could be turned into a parfor loops using ox+r for some value x but my PARI and computer both are useless for parallel computation.

[Batalov]

Originally Posted by wombatman

Based on how fast everything's going, I'll go ahead and run up to n=30k if that's alright.

I'll run 30-50k or until the first prime in that interval ;-)

[wombatman]

Originally Posted by Batalov

I'll run 30-50k or until the first prime in that interval ;-)

Sounds good! I'll go ahead and do 50-70k. No primes found up to n=30k.

[Batalov]

Here is the sieve for you - attached, if you want.