A234972 -id:A234972 - cp's OEIS frontend

A236966 Number of primes p < prime(n)/2 such that 2^p - 1 is a primitive root modulo prime(n).

0, 0, 1, 1, 1, 1, 3, 2, 1, 3, 2, 1, 2, 2, 5, 6, 3, 4, 3, 5, 4, 5, 7, 9, 3, 5, 2, 10, 7, 7, 7, 7, 9, 5, 10, 4, 5, 7, 12, 11, 14, 6, 7, 5, 10, 9, 8, 5, 12, 15, 14, 8, 12, 11, 16, 12, 16, 9, 12, 10, 10, 14, 15, 10, 12, 14, 9, 10, 21, 9, 22, 21, 11, 9, 18, 24, 20, 17, 17, 16

Offset: 1

Zhi-Wei Sun, Apr 22 2014

nonn

Conjecture: a(n) > 0 for all n > 2. In other words, for any prime p > 3, there is a prime q < p/2 with the Mersenne number 2^q - 1 a primitive root modulo p.
We have verified this for all n = 3, ..., 530000.
See also the comment in A234972.

			a(12) = 1 since 17 is a prime smaller than prime(12)/2 = 37/2 with 2^(17) - 1 = 131071 a primitive root modulo prime(12) = 37.

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

Cf. A000040, A001348, A001918, A234972, A235709, A235712, A236306, A236308.

f[k_]:=2^(Prime[k])-1
dv[n_]:=Divisors[n]
Do[m=0;Do[If[Mod[f[k],Prime[n]]==0,Goto[aa],Do[If[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,PrimePi[(Prime[n]-1)/2]}];Print[n," ",m];Continue,{n,1,80}]

A236308 Number of primes q < prime(n)/2 such that the Catalan number C(q) is a primitive root modulo prime(n).

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 1, 4, 2, 1, 4, 1, 3, 3, 5, 5, 5, 2, 4, 5, 4, 10, 4, 7, 7, 4, 7, 4, 9, 5, 6, 10, 9, 7, 5, 5, 12, 12, 13, 12, 4, 10, 7, 13, 4, 7, 10, 18, 9, 14, 13, 9, 9, 15, 17, 16, 8, 9, 12, 10, 19, 13, 10, 14, 14, 13, 6, 18, 18, 14, 24, 13, 16, 9, 22, 20, 12, 23, 15

Offset: 1

Zhi-Wei Sun, Apr 21 2014

nonn

Conjecture: a(n) > 0 for all n > 2. In other words, for any prime p > 3, there exists a prime q < p/2 such that the Catalan number C(q) = binomial(2q, q)/(q+1) is a primitive root modulo p.

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

			a(13) = 1 since C(7) = 429 is a primitive root modulo prime(13) = 41.

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

Cf. A000040, A000108, A234972, A235709, A235712, A236306, A236966.

f[k_]:=CatalanNumber[Prime[k]]
dv[n_]:=Divisors[n]
Do[m=0;Do[If[Mod[f[k],Prime[n]]==0,Goto[aa],Do[If[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,PrimePi[(Prime[n]-1)/2]}];Print[n," ",m];Continue,{n,1,80}]

A237112 Number of primes p < prime(n)/2 with p! a primitive root modulo prime(n).

Original entry on oeis.org

0, 0, 1, 0, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 6, 4, 2, 3, 3, 4, 7, 9, 5, 7, 5, 8, 4, 7, 6, 7, 8, 7, 11, 8, 9, 7, 13, 10, 16, 4, 7, 8, 13, 9, 8, 12, 17, 10, 14, 12, 4, 10, 14, 15, 18, 8, 9, 8, 8, 18, 6, 8, 7, 16, 9, 11, 21, 15

Offset: 1

Zhi-Wei Sun, Apr 22 2014

nonn

Conjecture: a(n) > 0 for all n > 4. In other words, for any prime p > 7, there exists a prime q < p/2 such that q! is a primitive root modulo p.

See also A236306 for a similar conjecture.

			a(7) = 1 since 3 is a prime smaller than prime(7)/2 = 17/2 and 3! = 6 is a primitive root modulo prime(7) = 17.
a(9) = 1 since  5 is a prime smaller than prime(9)/2 = 23/2 and 5! = 120 is a primitive root modulo prime(9) = 23.

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

Cf. A000040, A000142, A234972, A235709, A235712, A236306, A236308, A236966, A237121.

f[k_]:=(Prime[k])!
dv[n_]:=Divisors[n]
Do[m=0;Do[Do[If[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,PrimePi[(Prime[n]-1)/2]}];Print[n," ",m];Continue,{n,1,70}]

A235709 Least prime p < prime(n) with 2^p - 1 a quadratic residue modulo prime(n), or 0 if such a number does not exist.

Original entry on oeis.org

0, 0, 0, 0, 2, 2, 7, 3, 2, 3, 3, 2, 5, 5, 2, 3, 2, 2, 7, 2, 2, 5, 2, 23, 2, 5, 3, 2, 2, 3, 5, 2, 3, 3, 3, 5, 2, 11, 2, 5, 2, 2, 2, 2, 3, 3, 11, 3, 2, 2, 3, 2, 2, 2, 5, 2, 7, 3, 2, 3, 3, 5, 3, 2, 2, 3, 5, 2, 2, 2, 7, 2, 3, 2, 7, 2, 3, 2, 3, 2, 2, 2, 2, 2, 3, 2, 3, 2, 11, 5, 2, 2, 5, 2, 5, 2, 7, 5, 3, 2

Offset: 1

Zhi-Wei Sun, Apr 20 2014

nonn

Conjecture: a(n) > 0 for all n > 4.
We have verified this for all n = 5, ..., 10^8.
Note that the conjecture in A234972 implies that for any prime p > 3 there is a prime q < p with 2^q - 1 a quadratic nonresidue modulo p.

			a(8) = 3 since 2^3 - 1 = 7 is a quadratic residue modulo prime(8) = 19, but 2^2 - 1 = 3 is not.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Cf. A000040, A001348, A234972.

Do[Do[If[JacobiSymbol[2^(Prime[k])-1,Prime[n]]==1,Print[n," ",Prime[k]];Goto[aa]],{k,1,n-1}];Print[n," ",0];Label[aa];Continue,{n,1,100}]

A235712 Least prime p < prime(n) with 2^p + 1 a quadratic nonresidue modulo prime(n), or 0 if such a prime p does not exist.

Original entry on oeis.org

0, 2, 0, 2, 7, 2, 2, 5, 2, 11, 11, 2, 7, 2, 2, 2, 5, 5, 2, 5, 2, 5, 2, 5, 2, 7, 2, 2, 5, 2, 2, 13, 2, 5, 13, 5, 2, 2, 2, 2, 5, 11, 5, 2, 2, 7, 5, 2, 2, 23, 2, 7, 5, 5, 2, 2, 5, 5, 2, 7, 2, 2, 2, 5, 2, 2, 7, 2, 2, 5, 2, 7, 2, 2, 11, 2, 5, 2, 5, 5, 5, 7, 7, 2, 5, 2, 5, 2, 7, 2, 2, 7, 2, 13, 7, 2, 5, 5, 2, 5

Offset: 1

Zhi-Wei Sun, Apr 20 2014

nonn

Conjecture: a(n) > 0 for all n > 3.
Note that 2^3 + 1 = 3^2 is a quadratic residue modulo any prime p > 3. Also, there is no prime p < prime(316) = 2089 with 2^p + 1 a primitive root modulo 2089.
See also A234972 and A235709 for similar conjectures.

			a(4) = 2 since 2^2 + 1 = 5 is a quadratic nonresidue modulo prime(4) = 7.

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

Cf. A000040, A098640, A234972, A235709.

Do[Do[If[JacobiSymbol[2^(Prime[k])+1,Prime[n]]==-1,Print[n," ",Prime[k]];Goto[aa]],{k,1,n-1}];
Print[n," ",0];Label[aa];Continue,{n,1,100}]

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

Original entry on oeis.org

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

Zhi-Wei Sun, May 11 2014

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

			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.

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

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

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

A236306 Least prime p < prime(n) for which both p and p! are primitive roots modulo prime(n), or 0 if such a prime does not exist.

Original entry on oeis.org

0, 2, 2, 0, 2, 2, 3, 2, 5, 2, 11, 2, 17, 5, 5, 2, 2, 2, 2, 13, 5, 3, 2, 3, 5, 2, 11, 2, 67, 3, 3, 2, 3, 2, 2, 13, 53, 2, 5, 2, 2, 2, 47, 5, 2, 3, 2, 3, 2, 29, 3, 7, 137, 11, 3, 5, 2, 59, 31, 13, 17, 2, 5, 23, 47, 2, 101, 23, 2, 2, 13, 7, 43, 2, 2, 5, 2, 109, 3, 127

Offset: 1

Zhi-Wei Sun, Apr 21 2014

nonn

Conjecture: a(n) > 0 for all n > 4. In other words, for any prime p > 7, there exists a prime q < p such that both q and q! are primitive roots modulo p.

P. Erdős asked whether for any sufficiently large prime p there exists a prime q < p which is a primitive root modulo p (see page 377 of Guy's book in the reference).

			a(7) = 3 since both 3 and 3! = 6 are primititive roots modulo prime(7) = 17, but 2 is not a primitive root modulo 17.

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

Cf. A000040, A000142, A234972, A235709, A235712.

f[k_]:=Prime[k]!
dv[n_]:=Divisors[n]
Do[Do[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}];Print[n," ",Prime[k]];Goto[bb];Label[aa];Continue,{k,1,n-1}];Print[n," ",0];Label[bb];Continue,{n,1,80}]

A242242 Least positive primitive root g < prime(n) modulo prime(n) with 2^g - 1 also a primitive root modulo prime(n), or 0 if such a number g does not exist.

Original entry on oeis.org

1, 0, 2, 5, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2

Offset: 1

Zhi-Wei Sun, May 09 2014

nonn

Conjecture: a(n) > 0 except for n = 2. In other words, for any prime p > 3, there exists a primitive root 0 < g < p modulo p such that 2^g - 1 is also a primitive root modulo p.

			a(4) = 5 since both 5 and 2^5 - 1 = 31 are primitive roots modulo prime(4) = 7, but none of 1, 2, 4 and 2^3 - 1 is a primitive root modulo prime(4) = 7.

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

Cf. A000040, A000225, A234972, A236966.

f[n_]:=f[n]=2^n-1
dv[n_]:=Divisors[n]
Do[Do[If[Mod[f[k],Prime[n]]==0,Goto[aa]];Do[If[Mod[k^(Part[dv[Prime[n]-1],j])-1,Prime[n]]==0,Goto[aa]],{j,1,Length[dv[Prime[n]-1]]-1}];Do[If[rMod[f[k]^(Part[dv[Prime[n]-1],i])-1,Prime[n]]==0,Goto[aa]],{i,1,Length[dv[Prime[n]-1]]-1}];
Print[n," ",k];Goto[bb];Label[aa];Continue,{k,1,Prime[n]-1}];Label[cc];Print[n," ",0];Label[bb];Continue,{n,1,70}]

cp's OEIS Frontend

A236966 Number of primes p < prime(n)/2 such that 2^p - 1 is a primitive root modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A236308 Number of primes q < prime(n)/2 such that the Catalan number C(q) is a primitive root modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A237112 Number of primes p < prime(n)/2 with p! a primitive root modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A235709 Least prime p < prime(n) with 2^p - 1 a quadratic residue modulo prime(n), or 0 if such a number does not exist.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A235712 Least prime p < prime(n) with 2^p + 1 a quadratic nonresidue modulo prime(n), or 0 if such a prime p does not exist.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A236306 Least prime p < prime(n) for which both p and p! are primitive roots modulo prime(n), or 0 if such a prime does not exist.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A242242 Least positive primitive root g < prime(n) modulo prime(n) with 2^g - 1 also a primitive root modulo prime(n), or 0 if such a number g does not exist.

Views

Author

Keywords

Comments

Examples

Links