mersenneforum.org Dumb sieving question
 Register FAQ Search Today's Posts Mark Forums Read

 2017-11-26, 22:03 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×3,191 Posts Dumb sieving question 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 Last fiddled with by fivemack on 2017-11-26 at 22:03
2017-11-26, 22:27   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

296016 Posts

Quote:
 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.

2017-11-26, 22:57   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5·172 Posts

Quote:
 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.

 2017-11-26, 23:36 #4 rogue     "Mark" Apr 2003 Between here and the 141468 Posts 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.
2017-11-27, 02:22   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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).

Last fiddled with by science_man_88 on 2017-11-27 at 02:53

 2017-11-27, 21:01 #6 bsquared     "Ben" Feb 2007 3,371 Posts Code: 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... Last fiddled with by bsquared on 2017-11-27 at 21:39
2017-11-27, 21:39   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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

2017-11-27, 22:48   #8
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

22×227 Posts

Quote:
 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...
Code:
# 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

Last fiddled with by danaj on 2017-11-27 at 22:49

 Similar Threads Thread Thread Starter Forum Replies Last Post 1111GD1111 Information & Answers 2 2016-09-01 17:46 davieddy Science & Technology 9 2012-02-23 10:53 davieddy Information & Answers 17 2011-08-06 13:34 pacionet Math 2 2007-09-06 03:16 ThomRuley LMH > 100M 3 2004-06-11 02:02

All times are UTC. The time now is 20:15.

Thu Mar 4 20:15:32 UTC 2021 up 91 days, 16:26, 0 users, load averages: 1.39, 1.56, 1.65