A242345 Number of primes p < prime(n) with p and 2^p - p both primitive roots modulo prime(n).

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

Offset: 1

Author

Zhi-Wei Sun, May 11 2014

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 both q and 2^q - q are primitive roots modulo p.

According to page 377 in Guy's book, 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(4) = 1 since 3 is a prime smaller than prime(4) = 7, and both 3 and 2^3 - 3 = 5 are primitive roots modulo 7.
a(10) = 1 since 2 is a prime smaller than prime(10) = 29, and 2 and 2^2 - 2 are primitive roots modulo 29.
a(36) = 1 since 71 is a prime smaller than prime(36) = 151, and both 71 and 2^(71) - 71 ( == 14 (mod 151)) are primitive roots modulo 151.
		

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..3500
• Zhi-Wei Sun, Notes on primitive roots modulo primes, arXiv:1405.0290 [math.NT], 2014.

Crossrefs

Cf. A000040, A000325, A234972, A236966, A242248, A242250, A242292.

Programs

Mathematica

f[k_]:=2^(Prime[k])-Prime[k]
dv[n_]:=Divisors[n]
Do[m=0;Do[If[Mod[f[k],Prime[n]]==0,Goto[aa],Do[If[Mod[(Prime[k])^(Part[dv[Prime[n]-1],i]),Prime[n]]==1||Mod[f[k]^(Part[dv[Prime[n]-1],i]),Prime[n]]==1,Goto[aa]],{i,1,Length[dv[Prime[n]-1]]-1}]];m=m+1;Label[aa];Continue,{k,1,n-1}];
Print[n," ",m];Continue,{n,1,80}]