[synhrdhu] Artin's constant

what proportion of primes have 2 as a primitive root (generator)?  Pari/GP:

? ct=0; n=0; startp=10^8; forprime(p=prime(startp), prime(startp-1+10^8), n+=1; if(2==znprimroot(p), ct+=1)); print(ct," ",n);
37395647 100000000
time = 11min, 14,860 ms.

because 2 is squarefree and a prime not of the form 4k+1, the proportion is conjectured to be Artin's constant, computed by others as approximately 0.3739558.  (generators which don't satisfy those conditions are more complicated; see 5 below.)  according to Wikipedia, there is a conditional proof of the conjecture, conditional on the Generalized Riemann Hypothesis.

the reciprocal of Artin's constant is about 2.67 .  this is the factor of extra work required to find a random prime with primitive root 2 versus finding any random prime.  it's not that much extra work.

we sample starting from prime number startp to avoid potential unusual density among small numbers.  however, it turns out not to matter.

? ct=0; n=0; startp=1; forprime(p=prime(startp), prime(startp-1+10^8), n+=1; if(2==znprimroot(p),ct+=1)); print(ct," ",n);
37395252 100000000
time = 9min, 20,792 ms.

next, demonstrating on 5, a prime of the form 4k+1.  we use isprimroot_approx.  despite the name "approx", the result is exact for primes less than the MPQS threshold 2^220 in factor_partial.  isprimroot_approx only works correctly on primes, which is why we selected 5.

? c=0; n=0; startp=100; forprime(p=prime(startp), prime(startp-1+10^8), n+=1; if(isprimroot_approx(5,p), c+=1)); print(c," ",n)
39363667 100000000
time = 17min, 49,107 ms.

the expected answer for 5 is r = (Artin's Constant)*(1 + 1/(5^2-5-1)) = (Artin's Constant) * 20/19 ~= 0.393637699 .  standard deviation is sqrt(n*r*(1-r))/n ~= 0.000049 .