20171126, 22:03  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
2×3,191 Posts 
Dumb sieving question
Is there a tool that will sieve forms like 10^200k (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 20171126 at 22:03 
20171126, 22:27  #2 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2960_{16} Posts 

20171126, 22:57  #3  
"Robert Gerbicz"
Oct 2005
Hungary
5·17^{2} Posts 
Quote:
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. 

20171126, 23:36  #4 
"Mark"
Apr 2003
Between here and the
14146_{8} 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.

20171127, 02:22  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
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 20171127 at 02:53 

20171127, 21:01  #6 
"Ben"
Feb 2007
3,371 Posts 
Code:
time ./yafu "sieverange(10^20010^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 Not sure how this compares with other options... Last fiddled with by bsquared on 20171127 at 21:39 
20171127, 21:39  #7 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
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

20171127, 22:48  #8  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}×227 Posts 
Quote:
Code:
# Arguments are base, width, depth $ time perl Mbigint Mntheory=:all E 'say for sieve_range(1e2001e10,1e10,1e9);' > /tmp/f1 real 5m31.015s user 4m46.138s sys 0m31.133s On my Mac, Perl/ntheory sieve_range is 4080% faster than yafu's sieverange, but each one has known overhead that could be optimized away. Using sieverange(10^20010^9,10^200,10^10,0) vs sieve_range(1e2001e9,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 20171127 at 22:49 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Newbie here.....dumb question?  1111GD1111  Information & Answers  2  20160901 17:46 
Is this a dumb question?  davieddy  Science & Technology  9  20120223 10:53 
Ask a dumb question...  davieddy  Information & Answers  17  20110806 13:34 
LL Test : dumb question  pacionet  Math  2  20070906 03:16 
Dumb question time...  ThomRuley  LMH > 100M  3  20040611 02:02 