Dumb sieving question

[fivemack]

Is there a tool that will sieve forms like 10^200-k (say k=1..10^10)? I can't see how to do it with newpgen but I wouldn't be sure I'm not missing something obvious

[xilman]

Originally Posted by fivemack

Is there a tool that will sieve forms like 10^200-k (say k=1..10^10)? I can't see how to do it with newpgen but I wouldn't be sure I'm not missing something obvious

That's a brilliant question if ever I saw one.

[R. Gerbicz]

Originally Posted by fivemack

Is there a tool that will sieve forms like 10^200-k (say k=1..10^10)? I can't see how to do it with newpgen but I wouldn't be sure I'm not missing something obvious

My antique polysieve code handle this: https://sites.google.com/site/robertgerbicz/polysieve

use P(s)=s and Q(s)=-1 with s=10^200 using the only one c=0 value. [ "a" is positive that is why we needed to set Q(s)=-1 ]. Not saying it is the fastest, but it should be working.

[rogue]

A while ago I wrote a program called fnsievecl. I believe that will do what you want, but it has been a long time, so I'd have to look at the source again.

[science_man_88]

Originally Posted by fivemack

Is there a tool that will sieve forms like 10^200-k (say k=1..10^10)? I can't see how to do it with newpgen but I wouldn't be sure I'm not missing something obvious

obvious rules I see are:

1) k can't be divisible by factors of the base,
2)k also can't be a eulerphi of a prime ( or the euler phi mod that prime) when the exponent divides by that eulerphi because then you get that it divides by the prime in question.

edit: of course this form is just k*b^n+/-c where k=1.

and all that leads to k in your original statement has very few values in the range if the base is highly composite and the exponent is highly composite to values eulerphi can take on mod odd primes ( 2 fails the test, at least for this exponent and base pair.) aka the set one less than odd primes).

[bsquared]

time ./yafu "sieverange(10^200-10^10,10^200,10^9,0)" -pfile -v -v

>> computing: 99%
ans = 270943654

286.038u 24.949s 9:17.52 55.7%  0+0k 0+106366552io 1pf+0w

takes about 9 minutes to produce a file named sieved_values.dat containing the 270943654 surviving candidates between 10^200-10^10 and 10^200, after sieving by all primes < 10^9. The routine is meant to be general purpose; as a result, only about 5% or so of the 53 GB of output are not the number '9', but this could probably be fixed if desired.

Not sure how this compares with other options...

[science_man_88]

Originally Posted by science_man_88

2)k also can't be a eulerphi of a prime ( or the euler phi mod that prime) when the exponent divides by that eulerphi because then you get that it divides by the prime in question.

okay this only works for the +c versions it's -eulerphi for the minus c versions and even with those two I can elminate 70.72% roughly for the version of 10^200+k

[danaj]

Originally Posted by bsquared

[...]
takes about 9 minutes to produce a file named sieved_values.dat containing the 270943654 surviving candidates between 10^200-10^10 and 10^200, after sieving by all primes < 10^9. The routine is meant to be general purpose; as a result, only about 5% or so of the 53 GB of output are not the number '9', but this could probably be fixed if desired.

Not sure how this compares with other options...

# Arguments are base, width, depth
$ time perl -Mbigint -Mntheory=:all -E 'say for sieve_range(1e200-1e10,1e10,1e9);' > /tmp/f1

real	5m31.015s
user	4m46.138s
sys	0m31.133s

Output is integer offset from the base. Getting the full results can be done using sieve_primes(start, end, depth) but as you point out it takes lots of time just writing out the base for each number. It's even worse because this turns the full list into strings and then returns them all as a giant Perl array which is then printed. Way too much overhead.

On my Mac, Perl/ntheory sieve_range is 40-80% faster than yafu's sieverange, but each one has known overhead that could be optimized away.

Using sieverange(10^200-10^9,10^200,10^10,0) vs sieve_range(1e200-1e9,1e9,1e10) to spend more time sieving and less writing, I got 23359557 results in:
2m7.7s yafu
1m8.5s Perl/ntheory