mersenneforum.org Prime Gap Theory
 Register FAQ Search Today's Posts Mark Forums Read

 2016-01-17, 08:28 #1 robert44444uk     Jun 2003 Oxford, UK 2·7·137 Posts Prime Gap Theory This thread captures theory about prime gaps, links to key mathematical papers etc
 2016-02-05, 22:47 #2 mart_r     Dec 2008 you know...around... 11568 Posts How difficult is it to find a merit >= x? While I'm pausing my search for prime gaps, I've put together a small Pari program that can help finding optimal parameters for prime gap searches using primorial numbers. It compares the actually targetted merit to an "effective merit", meaning how hard it is to find from a statistical point of view. The average number of trials to find one merit > x symmetrical around the selected center number is then exp(corresponding effective merit). Thus, you can see what parameters have a positive (or negative) effect on the numbers you are searching, or the magnitude of the merit you want to find. I hope it is instructive enough. I've only taken about three hours to put it together. Ideas for improvements are welcome (though I can't really promise I'm able to implement all of them:). Code: print("merit(p [,d [,m [,u ] ] ] ):") print("set center number p#") print("optional d as divisor (default = 2)") print("optional m as multiplier (default = 1)") print("optional u as upper bound for merit calculation (default = 20)") print() print("Example: merit(9973,2*3*5*7,,30) calculates 9973#/210 for merits up to 30") print() print("-> Be sure to set allocatemem(x) with x>180*p if p>22000 (resp. x>9*u*p) ! <-") print() merit(p,d,m,u)={ if(!m,m=1); if(!d, d=2; print("set d to 2 by default") ); if(d%2, d=d+1; print("set d to "d) ); e=factor(d); i=1; for(s=1,#e[,1], i=i*e[s,2] ); if(i>1 || pn*log(r), print("merit "n" = effective merit "c/w/log(r)); n=n+1 ); c=c+a[s]+b[s] ) ) } I just noticed, for V1.1, I really should make the sieve more compact. Maybe tomorrow.
2016-02-05, 23:15   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by mart_r (though I can't really promise I'm able to implement all of them:)
my problem is although I know of ways in theory you could do the same I don't know what is the fastest a lot of the forsteps with 1 step in the step values could all be turned into for or parfor in newer versions of pari perhaps also the forprimes could be written as parforprimes depending on how many threads and cores the person running it has etc.

Code:
 if(d%2,
d=d+1;
print("set d to "d)
);
can be turned into:

Code:
d=d+d%2;
print("set d to "d);
edit: which can then be turned into ( and probably even shortened more by printing and assigning value in the same statement):

Code:
d+=d%2;
print("set d to "d);
a few things like:

Code:
i=i*e[s,2]
or
Code:
floor(2^z/3)
can be shortened in length ( number of typed keys)

Code:
forstep(s=t,z,q,a[s]=0);
forstep(s=v,z,q,b[s]=0)
could be turned into one loop with a few short calculations:

other than shortening things ( admittedly which I don't do), or parallel code, I still haven't looked at what it's doing ( I bet I couldn't figure it out if I tried). edit: oh and at least one of the forprime loops can be replaced with factorback(primes([2,p])) the prints at the start can be combined together into one with \n in it to symbolize the new lines. anyways I'm not really helping optimization. edit: is
Code:
for(s=1,#e[,1],i*=e[s,2]);if(i>1
a faster form of issquarefree ? if so e is not needed for that part and i may not be needed in that part either that may free up some memory. I'll see what else I can think of. doh I see why you did that loop and then checked i you used the factorization of d in the || part so you needed it so it was faster to check if all the values of e[,2] are 1 which can be done without the loop still admittedly but at least I realized the reason calling issquarefree would likely factor the number again costing more time.

Last fiddled with by science_man_88 on 2016-02-05 at 23:51

 2016-02-06, 03:20 #4 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2·3·151 Posts I think discussion of what one can do with the script would be more useful than its performance. It runs essentially instantly, so it would only matter if one were running it many thousands of times (which would mean modifications since it currently generates many lines of output per run).
 2016-02-07, 18:57 #5 mart_r     Dec 2008 you know...around... 62210 Posts @ science_man_88: Thanks for your comments. Strangely, last time I checked, "a=a+1" or "a=a*2" was slightly faster than "a+=1" or "a*=2", but I've done yet another check today with a different result. I adopted the shorter version now anyway. Your version for the d%2 case works a bit differently than mine, so I didn't change that. I haven't looked into the "issquarefree" function, but I agree, though it is surely faster than a normal factorisation, it is still slower than a quick check on the powers in the factorization which I already need to look for the biggest prime factor of the divisor d. Also, though there may be more recently implemented functions which are faster, I vote for downward compatibility :) I'm more content with the program now. It can keep track of a certain specified merit value during a predefined loop, so it essentially works like my former VBA-program, albeit more user-friendly. Code: print() print("merit(p [,d [,m [,u [,tr ] ] ] ] ):") print(" set center number p#") print(" optional d as divisor (default = 2)") print(" optional m as multiplier (default = 1)") print(" optional u as upper bound for merit calculation (default = 20)") print(" optional tr: track values for a specific merit in file 'merit [tr]'") print() print(" Example: merit(9973,2*3*5*7,,30) calculates 9973#/210 for merits up to 30") print() print("-> Be sure to set allocatemem(x) with x>90*p if p>44000 (resp. x>5*u*p) ! <-") print() merit(p,d,m,u,tr)={ if(!m,m=1); if(!d, d=2; print("set d to 2 by default") ); if(d%2, d+=1; print("set d to "d) ); e=factor(d); i=1; for(s=1,#e[,1], i*=e[s,2] ); if(i>1 || pn/4*log(r), o=Str("merit "n" = effective merit "c/w/log(r)); print(o); if(tr==n, write("merit "tr".txt",m"*"p"#/"d" : "o,Strchr(13)) ); n+=1 ); c+=a[s]+b[s] ) ) }
2016-02-07, 19:45   #6
Antonio

"Antonio Key"
Sep 2011
UK

32·59 Posts

Quote:
 Originally Posted by mart_r;425557 [CODE if(d%2, d+=1; print("set d to "d) ); [/CODE]
I don't understand why you force the divisor to be even?
If I want the divisor to be, say, 3*5 then you force it to become 15+1 = 16 which will (should) then fail as not dividing p#.
Any divisor, d, even 1, should be legitimate, as long as: -
1) d has no repeated factors
2) the largest factor of d is less than or equal to p
and
3) d < p#

2016-02-07, 19:57   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by mart_r @ science_man_88: Thanks for your comments. Strangely, last time I checked, "a=a+1" or "a=a*2" was slightly faster than "a+=1" or "a*=2", but I've done yet another check today with a different result. I adopted the shorter version now anyway. Your version for the d%2 case works a bit differently than mine, so I didn't change that. I haven't looked into the "issquarefree" function, but I agree, though it is surely faster than a normal factorisation, it is still slower than a quick check on the powers in the factorization which I already need to look for the biggest prime factor of the divisor d. Also, though there may be more recently implemented functions which are faster, I vote for downward compatibility :) I'm more content with the program now. It can keep track of a certain specified merit value during a predefined loop, so it essentially works like my former VBA-program, albeit more user-friendly.

Last fiddled with by science_man_88 on 2016-02-07 at 20:50

2016-02-08, 20:04   #8
mart_r

Dec 2008
you know...around...

2·311 Posts

Quote:
 Originally Posted by Antonio I don't understand why you force the divisor to be even? If I want the divisor to be, say, 3*5 then you force it to become 15+1 = 16 which will (should) then fail as not dividing p#. Any divisor, d, even 1, should be legitimate, as long as: - 1) d has no repeated factors 2) the largest factor of d is less than or equal to p and 3) d < p#
Doesn't an odd divisor make the search for such gaps dramatically ineffective?
The sieve also only looks for even numbers (well, that might be easily changed, I guess).

Admittedly, to be consistent, I should've just halted the program for an odd input of d and not try to change it automatically. I'm still learning...

2016-02-09, 18:42   #9
Antonio

"Antonio Key"
Sep 2011
UK

32×59 Posts

Quote:
 Originally Posted by mart_r Doesn't an odd divisor make the search for such gaps dramatically ineffective? The sieve also only looks for even numbers (well, that might be easily changed, I guess). Admittedly, to be consistent, I should've just halted the program for an odd input of d and not try to change it automatically. I'm still learning...
It depends on your definition of 'ineffective'.

To explain I will define the following (just to be clear):-

for prime, p, and divisor, d, with multiplier, i, relative prime to d
we compute C = i * p# / d
then:
P1 = prev_prime(C)
P2 = next_prime(C)
gap = P2 - P1

As an example, I have a version of Dana's code which searches over a specified digit range of C.

If I use this with parameters:
i from 1e5 to 2e5
C from 20 to 100 digits
d = 24090 (2*3*5*11*73)
and record the number of values found with merit > 20
the program finds 216 (from 789096 possible)
i.e. 3653 tries per result

If I then use d = 12045 (3*5*11*73), all other parameters unchanged, then
the program finds 272 (from 1578093 possible)
i.e. 5802 tries per result.

I will leave you to decide if that is ineffective or not .

 2016-02-10, 07:49 #10 Antonio     "Antonio Key" Sep 2011 UK 21316 Posts Just to add (too late for edit) that the program chose p to be over the range p = 73 to p = 241 (inclusive).
 2016-02-10, 21:19 #11 mart_r     Dec 2008 you know...around... 2×311 Posts @ sm88: You surely are concerned about my program :) (and nearly doubled the number of messages in my PM inbox ;) I've changed a few things today and thereby made it quite a bit faster, especially "l=log(r)/4" outside the output loop helped a lot. Also, fixed the main concern about odd inputs of d. Apart from some cosmetics (maybe addhelp sometime later...), how's it now? Code: print() print("merit(p [,d [,m [,u [,tv ] ] ] ] ):") print(" set center number p#") print(" optional d as divisor (default = 2)") print(" optional m as multiplier (default = 1)") print(" optional u as upper bound for merit calculation (default = 20)") print(" optional tv: track values for a specific merit in file 'merit [tv]'") print() print(" Example: merit(9973,2*3*5*7,,30) calculates 9973#/210 for merits up to 30") print() print("-> Be sure to set allocatemem(x) with x>90*p if p>44000 (resp. x>5*u*p) ! <-") print() merit(p,d,m,u,tv)={ if(!m,m=1); if(d<1, d=2; print("set d to 2 by default") ); k=d%2; e=factor(d); i=1; for(s=1,#e[,1], i*=e[s,2] ); if(i>1 || pn*l, o=Str("merit "n" = effective merit "c/(w*log(r))); print(o); if(tv==n, write("merit "tv".txt",m"*"p"#/"d" : "o,Strchr(13)) ); n+=1 ); c+=a[s]+b[s] ) ) } Last fiddled with by mart_r on 2016-02-10 at 21:57 Reason: yet some quick modifications...

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 6 2016-10-14 19:38 firejuggler Math 0 2016-07-11 23:09 Ricie Miscellaneous Math 24 2009-08-14 15:31 jasong Math 3 2005-05-15 04:01 clowns789 Miscellaneous Math 5 2004-01-08 17:09

All times are UTC. The time now is 11:35.

Wed Jan 27 11:35:56 UTC 2021 up 55 days, 7:47, 0 users, load averages: 4.46, 4.93, 4.98