mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2017-11-26, 22:03   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23×797 Posts
Default 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
fivemack is offline   Reply With Quote
Old 2017-11-26, 22:27   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×5,197 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
xilman is offline   Reply With Quote
Old 2017-11-26, 22:57   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3×11×43 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2017-11-26, 23:36   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×3,019 Posts
Default

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.
rogue is online now   Reply With Quote
Old 2017-11-27, 02:22   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-11-27, 21:01   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

335210 Posts
Default

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
bsquared is offline   Reply With Quote
Old 2017-11-27, 21:39   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-11-27, 22:48   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts
Default

Quote:
Originally Posted by bsquared View Post
[...]
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
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Newbie here.....dumb question? 1111GD1111 Information & Answers 2 2016-09-01 17:46
Is this a dumb question? davieddy Science & Technology 9 2012-02-23 10:53
Ask a dumb question... davieddy Information & Answers 17 2011-08-06 13:34
LL Test : dumb question pacionet Math 2 2007-09-06 03:16
Dumb question time... ThomRuley LMH > 100M 3 2004-06-11 02:02

All times are UTC. The time now is 01:59.

Thu Dec 3 01:59:01 UTC 2020 up 83 days, 23:09, 1 user, load averages: 2.18, 2.38, 2.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.