hermann on Wed, 04 Jun 2025 21:50:54 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Probability of coprimality / GP random() |
Last week I visited Heidelberg University library. I found area where books on Algebra, analytic number theory, p-adic numbers, ... were located and picked 5 books. Looking through I learned about subject in one of the books. Now I found it on Wikipedia for reference: https://en.wikipedia.org/wiki/Coprime_integers#Probability_of_coprimality The probability is 6/Pi^2 (roughly 61%), and I tested GP. I am pretty sure that GP random() passes other primality tests as well. Nice to see that the results below seem to be as they should. The result of 6/Pi^2 is for computing the Basel problem. Today I found a nice geometrical "proof" for 6/Pi^2: https://www.youtube.com/watch?v=d-o3eB9sfls&t=635s And thought I might post here. Regards, Hermann. hermann@7950x:~$ gp -q ? # timer = 1 (on)? N=50000;M=10^100;c=0;for(i=1,N,if(gcd(random(M),random(M))==1,c+=1));print(c*1.0/N);print(6/Pi^2);
0.61004000000000000000000000000000000000 0.60792710185402662866327677925836583343 time = 65 ms.? N=500000;M=10^100;c=0;for(i=1,N,if(gcd(random(M),random(M))==1,c+=1));print(c*1.0/N);print(6/Pi^2);
0.60770200000000000000000000000000000000 0.60792710185402662866327677925836583343 time = 647 ms.? N=5000000;M=10^100;c=0;for(i=1,N,if(gcd(random(M),random(M))==1,c+=1));print(c*1.0/N);print(6/Pi^2);
0.60759480000000000000000000000000000000 0.60792710185402662866327677925836583343 time = 5,729 ms.? N=50000000;M=10^100;c=0;for(i=1,N,if(gcd(random(M),random(M))==1,c+=1));print(c*1.0/N);print(6/Pi^2);
0.60792814000000000000000000000000000000 0.60792710185402662866327677925836583343 time = 58,623 ms. ?