login
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).
4
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,3
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.
REFERENCES
R. K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, New York, 2004.
LINKS
Zhi-Wei Sun, New observations on primitive roots modulo primes, arXiv:1405.0290 [math.NT], 2014.
EXAMPLE
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.
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Aug 27 2017
STATUS
approved