Prime numbers with next characteristic

[Dr Sardonicus]

The following might be quicker than plowing through all the primes from 10^6 to 10^7 - 1, because it only looks at 9000 candidates. OK, I also cheated by using ispseudoprime().

v=vector(9000);t=1;for(i=1,9,for(j=0,9,for(k=0,9,for(l=0,9,n=i*10^6+11*(j*10^4+k*10^2+l);if(ispseudoprime(n),v[t]=n;t++)))));w=vector(t-1);for(i=1,t-1,w[i]=v[i]);print(w)

[axn]

Originally Posted by Dr Sardonicus

The following might be quicker than plowing through all the primes from 10^6 to 10^7 - 1, because it only looks at 9000 candidates. OK, I also cheated by using ispseudoprime().

v=vector(9000);t=1;for(i=1,9,for(j=0,9,for(k=0,9,for(l=0,9,n=i*10^6+11*(j*10^4+k*10^2+l);if(ispseudoprime(n),v[t]=n;t++)))));w=vector(t-1);for(i=1,t-1,w[i]=v[i]);print(w)

Removing the vector stuff and just counting the hits, your code runs in 6ms while mine runs in 385 ms. So they're basically the same

Actually, if you replace ispseudoprime with isprime, your code takes a whopping 6ms

[Dr Sardonicus]

Originally Posted by axn

Removing the vector stuff and just counting the hits, your code runs in 6ms while mine runs in 385 ms. So they're basically the same

Actually, if you replace ispseudoprime with isprime, your code takes a whopping 6ms

Although my computer is way slower, using isprime() instead of ispseudprime() still did not increase the runtime in ms on my machine. I didn't run the "plow through all the primes from 10^6 to 10^7" method. It's good to have a point of reference for the runtimes.

The number of primes between 10^6 and 10^7 is 586081. Dividing 586081 by 9000 gives 65.1201111. Dividing 385 ms by 6 ms gives 64.166666.So it looks to me like reducing the number of candidates is mainly responsible for the decrease in runtime.

[CRGreathouse]

Originally Posted by Dr Sardonicus

Although my computer is way slower, using isprime() instead of ispseudprime() still did not increase the runtime in ms on my machine.

I had Karim call ispseudoprime for all numbers below 2^64 since there are no BPSW pseudoprimes below that limit, so there's no runtime difference.

[ET_]

Originally Posted by CRGreathouse

I had Karim call ispseudoprime for all numbers below 2^64 since there are no BPSW pseudoprimes below that limit, so there's no runtime difference.

[danaj]

Below 2^64, there shouldn't be any difference in isprime and ispseudoprime. isprime() calls BPSW_isprime() which calls BPSW_isprime_small().

The value of not running through all the primes is more obvious if we extend this to larger variants, e.g. 4 or 5 repeated digits. Both of these are similar and pretty fast.

$ time perl -Mntheory=:all -E 'my(@v)=(1..9); for (1..5) { @v=map { my $t=$_; map {"$t$_$_"}0..9; } @v; } say scalar(grep { is_prime($_) } @v);'
40272

real	0m0.846s
user	0m0.770s
sys	0m0.065s

? v=vector(900000);t=1;for(x=1,9,for(i=0,9,for(j=0,9,for(k=0,9,for(l=0,9,for(m=0,9,n=x*10^10+11*(i*10^8+j*10^6+k*10^4+l*10^2+m);if(isprime(n),v[t]=n;t++)))))));w=vector(t-1);for(i=1,t-1,w[i]=v[i]);length(w)
time = 934 ms.
40272