A291615 Number of primes p < prime(n) such that p is a primitive root modulo prime(n) and also a primitive root modulo prime(p).

0, 1, 2, 1, 2, 3, 3, 3, 2, 3, 3, 2, 3, 1, 3, 3, 3, 2, 5, 3, 2, 2, 4, 5, 5, 5, 2, 3, 3, 3, 4, 2, 6, 3, 11, 4, 3, 8, 9, 8, 10, 7, 6, 3, 9, 6, 6, 6, 11, 10, 11, 9, 9, 9, 12, 11, 13, 3, 6, 10, 7, 15, 5, 6, 7, 13, 7, 8, 14, 10, 13, 19, 12, 14, 11, 18, 15, 11, 15, 8

Offset: 1

Author

Zhi-Wei Sun, Aug 27 2017

Keywords

• nonn

Comments

Conjecture: a(n) > 0 for all n > 1. In other words, for any odd prime p there is a prime q < p such that q is a primitive root modulo p and also a primitive root modulo prime(q).

According to page 377 in Guy's book, P. Erdős asked whether for any sufficiently large prime p there exists a prime q < p which is a primitive root modulo p.

Examples

			a(2) = 1 since the prime 2 < prime(2) = 3 is a primitive root modulo prime(2) = 3.
a(4) = 1 since the prime 3 < prime(4) = 7 is a primitive root modulo prime(4) = 7 and also a primitive root modulo prime(3) = 5.
a(14) = 1 since the prime 3 < prime(14) = 43 is a primitive root modulo prime(14) = 43 and also a primitive root modulo prime(3) = 5.
		

References

• R. K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, New York, 2004.

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..2000
• Zhi-Wei Sun, New observations on primitive roots modulo primes, arXiv:1405.0290 [math.NT], 2014.

Crossrefs

Cf. A000040, A242345, A243164, A243403.

Programs

Mathematica

rMod[m_,n_]:=rMod[m,n]=Mod[Numerator[m]*PowerMod[Denominator[m],-1,n],n,-n/2]
p[n_]:=p[n]=Prime[n];
Do[r=0;Do[Do[If[Mod[p[g]^(Part[Divisors[p[n]-1],i])-1,p[n]]==0,Goto[aa]],{i,1,Length[Divisors[p[n]-1]]-1}];
Do[If[Mod[p[g]^(Part[Divisors[p[p[g]]-1],j])-1,p[p[g]]]==0,Goto[aa]],{j,1,Length[Divisors[p[p[g]]-1]]-1}];
r=r+1;Label[aa],{g,1,n-1}];Print[n," ",r],{n,1,80}]