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,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, 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.

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

Cf. A000040, A242345, A243164, A243403.

Sequence in context: A002339 A123243 A037193 * A361789 A343040 A343044

Adjacent sequences: A291612 A291613 A291614 * A291616 A291617 A291618

Keyword

nonn

Author

Zhi-Wei Sun, Aug 27 2017

Status

approved