20180317, 11:44  #45  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
Last fiddled with by science_man_88 on 20180317 at 12:25 

20180317, 15:14  #46  
Feb 2017
Nowhere
3×7×13^{2} Posts 
Quote:
The coefficient 6/pi^2 is for the number of pairs of positive integer (a, b), both less than or equal to N, with gcd(a, b) = 1  but without the requirement a < b. This coefficient may be viewed as the limiting value, as N increases without bound, of the probability that two positive integers, chosen at random in [1, N], are relatively prime. By considering separately the possible prime common factors 2, 3, 5, etc and a bit of handwaving, you obtain the coefficient as being the product (1  1/2^2)*(1  1/3^2)*(1  1/5^2)... whose inverse is obviously the sum, from k = 1 to infinity, of 1/k^2, whose value is well known to be pi^2/6. Thus, the coefficient is 6/pi^2. Imposing the requirement a < b obviously cuts the number of pairs in half, giving the correct asymptotic for the Farey sequence of order N as 3/pi^2 * N^2. The coefficient 3/pi^2 is 0.30396355092701331433163838962918291671, approximately. Being too lazy either to work out or look up the variant with the further requirement that a and b be of different parity, I simply had PariGP find the actual value numerically up to some ridiculous limit, and print out the value every so often. It was interesting to watch as an increasing number of decimal digits remained fixed, but the convergence was slow, so I CtrlC'd it out of my misery. The asymptotic for the variant clearly is 2/pi^2 * N^2, the coefficient 2/pi^2 being 0.20264236728467554288775892641945527781 approximately. Last fiddled with by Dr Sardonicus on 20180317 at 15:23 

20180317, 17:00  #47  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
Last fiddled with by science_man_88 on 20180317 at 17:02 

20180318, 15:55  #48 
Feb 2017
Nowhere
3×7×13^{2} Posts 
Just for practice, I (tried to) write PariGP scripts to perform various tasks associated with this problem. I compiled a vector of all pairs [a, b] with b up to 200 for which
a < b, gcd(a, b) = 1, and a + b is odd. I deliberately left the testing of the conditions appallingly clumsy. Since I didn't bother to compute in advance how many pairs there were going to be, I used concat() to append each new pair to my vector. That took way more time than computing the pairs [a, b]. No matter, I had my vector of pairs, 8156 of them. If I had done the computation of the number of pairs in advance, this part of the operation would have been much faster. Next, I decided to see how effective sieving might be. Using the original exponent e = 2^14, I compiled a vector of primes p < 2^26, p congruent to 1 (mod 2^15). There are 228 of them. I then wrote a script that initialized a count at 0 and went through my vector of pairs [a,b]. If my script is writ right (I invite anyone to check the results, I'm not good at writing scripts), for each pair [a,b] it goes through my vector of primes p, and computes r = Mod(a,p)^e + Mod(b,p)^e. Then if r is zero, it increments the count, and immediately moves on to the next pair [a,b]. (I note that the smallest value 2^(2^14) + 1 of a^e + b^e is way bigger than my prime limit 2^26.) At the end of the run, the count of pairs sieved out was 4065. Now 4065./8156 = 0.4984, approximately. The "grasping at straws" product of (1.  2^14/p), taken over the 228 primes on my list, is 0.4995, approximately. That is much closer agreement than I had hoped for! Last fiddled with by Dr Sardonicus on 20180318 at 16:00 Reason: correcting wrong words 
20180318, 16:26  #49 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
my code for counting them was just:
Code:
my(a=0);for(x=1,200,forstep(y=x1,1,2,if(gcd(x,y)==1,a++)));a 
20180318, 17:12  #50 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,041 Posts 
Just in case, if anyone is sieiving or testing for m=17, a(17) > 238.

20180318, 17:20  #51 
Sep 2002
Database er0rr
2^{2}·859 Posts 

20180318, 19:47  #52  
Feb 2017
Nowhere
3·7·13^{2} Posts 
Quote:
Code:
? s=0;r=1;for(i=2,200,if(r,t=eulerphi(i),t=eulerphi(i)/2);s+=t;r=!r);print(s) 8156 time = 0 ms. Code:
? k=1;v=vector(s);for(j=2,200,for(i=1,j1,if((i+j)%2==1&&gcd(i,j)==1,v[k]=[i,j];k++))) time = 47 ms. ? print(v[s]) [199, 200] Last fiddled with by Dr Sardonicus on 20180318 at 19:53 

20180318, 20:04  #53 
"Rashid Naimi"
Oct 2015
Remote to Here/There
19×101 Posts 
My 2ยข worth,
The fastest filtering is size based since the objective is to find the smallest PRP. You can set a narrow test range based on size, assign each band to a different thread and advance upwards after each completion. The size filtering before any trial by division or PRP test seems most efficient to me. It should avoid a lot of unnecessary lager PRP tests. Last fiddled with by a1call on 20180318 at 20:08 
20180318, 20:19  #54  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
Last fiddled with by science_man_88 on 20180318 at 20:36 

20180318, 20:47  #55 
"Rashid Naimi"
Oct 2015
Remote to Here/There
19·101 Posts 
Chances are you can eliminate some 10's of very expensive PRP tests by performing a GCD test between each candidate :
GCD (a^q+b^q,(a+k)^+(b+k')^q) For arbitrary values of k and k'. Such a test can speed things up, but gets less and less effective as the exponent/PRP gets larger. There is not much saving if any, in doing more than one such test. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Is there a prime of the form......  PawnProver44  Miscellaneous Math  9  20160319 22:11 
OEIS A071580: Smallest prime of the form k*a(n1)*a(n2)*...*a(1)+1  arbooker  And now for something completely different  14  20150522 23:18 
Smallest prime with a digit sum of 911  Stargate38  Puzzles  6  20140929 14:18 
Smallest floor of k for cullen prime  Citrix  Prime Cullen Prime  12  20070426 19:52 
Smallest tenmilliondigit prime  Heck  Factoring  9  20041028 11:34 