A243164 -id:A243164 - cp's OEIS frontend

A243403 Number of primes p < n such that p*(n-p) is a primitive root modulo prime(n).

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

Offset: 1

Zhi-Wei Sun, Jun 04 2014

nonn

Conjecture: a(n) > 0 for all n > 6.

We have verified this for all n = 7, ..., 2*10^5.

			a(18) = 1 since 17 is prime with 17*(18-17) = 17 a primitive root modulo prime(18) = 61.
a(20) = 1 since 11 is prime with 11*(20-11) = 99 a primitive root modulo prime(20) = 71.
a(26) = 1 since 2 is prime with 2*(26-2) = 48 a primitive root modulo prime(26) = 101.
a(27) = 1 since 17 is prime with 17*(27-17) = 170 a primitive root modulo prime(27) = 103.

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

Cf. A000040, A000720, A243164.

dv[n_]:=Divisors[n]
Do[m=0;Do[Do[If[Mod[(Prime[k]*(n-Prime[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,PrimePi[n-1]}];
Print[n," ",m];Continue,{n,1,80}]

A243755 Primes p such that p is a primitive root modulo the next prime p' and also p' is a primitive root modulo p.

Original entry on oeis.org

2, 3, 5, 11, 59, 61, 83, 101, 131, 151, 179, 181, 197, 251, 257, 269, 271, 317, 337, 347, 367, 419, 443, 461, 523, 563, 577, 587, 593, 659, 709, 733, 797, 811, 821, 827, 863, 947, 971, 977, 1061, 1063, 1069, 1097, 1129, 1153, 1171, 1187, 1217, 1229, 1277, 1283, 1301, 1361, 1433, 1451, 1543, 1553, 1601, 1619

Offset: 1

Zhi-Wei Sun, Jun 09 2014

nonn

Conjecture: The sequence contains infinitely many primes. Moreover, there are infinitely many primes p such that both p and -p are primitive roots modulo the next prime p' and both p' and -p' are primitive roots modulo p.

			a(1) = 2 since prime(1) = 2 is a primitive root modulo prime(2) = 3 and also prime(2) = 3 is a primitive root modulo prime(1) = 2.
a(2) = 3 since prime(2) = 3 is a primitive root modulo prime(3) = 5 and also prime(3) = 5 is a primitive root modulo prime(2) = 3.

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

Cf. A000040, A243164, A243403.

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

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

Original entry on oeis.org

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

Zhi-Wei Sun, Aug 27 2017

nonn

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.

			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.

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

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.

Cf. A000040, A242345, A243164, A243403.

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

A291657 Primes p such that p is a primitive root modulo prime(p).

Original entry on oeis.org

2, 3, 7, 11, 13, 41, 71, 79, 83, 107, 109, 131, 139, 157, 163, 173, 179, 191, 211, 223, 229, 263, 271, 277, 293, 311, 313, 317, 337, 353, 359, 367, 373, 389, 419, 431, 439, 449, 457, 463, 479, 521, 547, 569, 577, 593, 607, 641, 661, 709, 719, 727, 743, 757, 761, 769, 787, 811, 823, 827

Offset: 1

Zhi-Wei Sun, Aug 28 2017

nonn

The conjecture in A291615 implies that the current sequence has infinitely many terms. In fact, if there are only finitely many primes p with p a primitive root modulo prime(p) and we let P denote the product of all such primes, then by Dirichlet's theorem there is a prime q == 1 (mod 4*P) and hence any prime p with p a primitive root modulo prime(p) is a quadratic residue modulo q and hence not a primitive root modulo q.

Conjecture: a(n)/(n*log(n)) has a positive limit as n tends to the infinity. Equivalently, all the terms in this sequence form a subset of the set of all primes with positive asymptotic density.

			a(1) = 2 since the first prime 2 is a primitive root modulo prime(2) = 3.
a(2) = 3 since the prime 3 is a primitive root modulo prime(3) = 5.

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

Cf. A000040, A242345, A243164, A243403, A291615, A291690.

p[n_]:=p[n]=Prime[n];
n=0;Do[Do[If[Mod[p[k]^(Part[Divisors[p[p[k]]-1],i])-1,p[p[k]]]==0,Goto[aa]],{i,1,Length[Divisors[p[p[k]]-1]]-1}];
n=n+1;Print[n," ",p[k]];Label[aa],{k,1,145}]

A291690 Least positive integer g which is a primitive root modulo prime(n) and also a primitive root modulo prime(n+1).

Original entry on oeis.org

5, 2, 3, 17, 2, 6, 3, 10, 10, 3, 13, 13, 12, 5, 5, 2, 2, 2, 7, 11, 28, 6, 6, 7, 7, 11, 5, 6, 6, 3, 6, 6, 3, 2, 12, 6, 18, 20, 5, 2, 2, 21, 19, 5, 3, 3, 3, 5, 6, 6, 21, 7, 14, 6, 5, 7, 15, 6, 11, 3, 3, 5, 22, 17, 14, 3, 29, 15, 2, 13, 13, 19, 6, 2, 10, 10, 18, 6, 21, 26

Offset: 1

Zhi-Wei Sun, Aug 29 2017

nonn

Clearly, a(n) < prime(n)*prime(n+1) by the Chinese Remainder Theorem. It seems that for any positive integer n other than 1, 4, 8 there is a prime p < prime(n) which is a primitive root modulo prime(n) and also a primitive root modulo prime(n+1).
Conjecture: (i) For any distinct primes p and q, there is a positive integer g not exceeding sqrt(4*p*q+1) such that g is a primitive root modulo p and also a primitive root modulo q. We may require further that g < sqrt(p*q) if {p,q} is not among the 15 pairs {2,3}, {2,11}, {2,13}, {2,59}, {2,131}, {2,181}, {3,7}, {3,31}, {3,79}, {3,191}, {3,199}, {5,271}, {7,11}, {7,13} and {7,71}.
(ii) For each integer n > 1, there is a constant c(n) > 0, such that for any n distinct primes p(1),...,p(n) there is a positive integer g < c(n)*(p(1)*...*p(n))^(1/n) which is a primitive root modulo p(k) for all k = 1,...,n.

			a(1) = 5 since 5 is a primitive root modulo prime(1) = 2 and also a primitive root modulo prime(2) = 3, but none of 1, 2, 3, 4 has this property.
a(2) = 2 since 2 is a primitive root modulo prime(2) = 3 and also a primitive root modulo prime(3) = 5.
a(4) = 17 since 17 is the least positive integer which is a primitive root modulo prime(4) = 7 and also a primitive root modulo prime(5) = 11.

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

Cf. A000040, A242345, A243164, A243403, A291615, A291657.

p[n_]:=Prime[n];
Do[g=0;Label[aa];g=g+1;If[Mod[g,p[n]]==0||Mod[g,p[n+1]]==0,Goto[aa]];Do[If[Mod[g^(Part[Divisors[p[n]-1],i])-1,p[n]]==0,Goto[aa]],{i,1,Length[Divisors[p[n]-1]]-1}];
Do[If[Mod[g^(Part[Divisors[p[n+1]-1],j])-1,p[n+1]]==0,Goto[aa]],{j,1,Length[Divisors[p[n+1]-1]]-1}];Print[n," ",g],{n,1,80}]

a(n,p=prime(n))=my(q=nextprime(p+1),g=2); while(gcd(g,p*q)>1 || znorder(Mod(g,p))Charles R Greathouse IV, Aug 30 2017

cp's OEIS Frontend

A243403 Number of primes p < n such that p*(n-p) is a primitive root modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A243755 Primes p such that p is a primitive root modulo the next prime p' and also p' is a primitive root modulo p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A291657 Primes p such that p is a primitive root modulo prime(p).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A291690 Least positive integer g which is a primitive root modulo prime(n) and also a primitive root modulo prime(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI