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

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.

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.

Example

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.

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}]

Crossrefs

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

Sequence in context: A023591 A165661 A107711 * A179067 A061893 A078530

Adjacent sequences: A242342 A242343 A242344 * A242346 A242347 A242348

Keyword

nonn

Author

Zhi-Wei Sun, May 11 2014

Status

approved