A237112 -id:A237112 - cp's OEIS frontend

A239957 a(n) = |{0 < g < prime(n): g is a primitive root modulo prime(n) of the form k^2 + 1}|.

1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 1, 3, 2, 2, 3, 4, 4, 4, 2, 1, 2, 1, 3, 3, 6, 3, 3, 7, 4, 5, 2, 8, 3, 5, 6, 1, 2, 5, 8, 10, 7, 3, 2, 6, 8, 2, 3, 5, 8, 4, 7, 4, 2, 5, 8, 9, 10, 5, 8, 6, 10, 6, 4, 9, 6, 9, 5, 3, 13, 5, 8, 9, 5, 6, 8, 13, 13, 6, 6, 5

Offset: 1

Zhi-Wei Sun, Apr 23 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 0. In other words, every prime p has a primitive root 0 < g < p of the form k^2 + 1, where k is an integer.
(ii) If p > 3 is a prime not equal to 13, then p has a primitive root 0 < g < p which is of the form k^2 - 1, where k is a positive integer.
See also A239963 for a similar conjecture.

			a(6) = 1 since 1^2 + 1 = 2 is a primitive root modulo prime(6) = 13.
a(11) = 1 since 4^2 + 1 = 17 is a primitive root modulo prime(11) = 31.
a(20) = 1 since 8^2 + 1 = 65 is a primitive root modulo prime(20) = 71.
a(22) = 1 since 6^2 + 1 = 37 is a primitive root modulo prime(22) = 79.
a(36) = 1 since 9^2 + 1 = 82 is a primitive root modulo prime(36) = 151.

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

Cf. A000040, A002522, A236308, A236966, A237112, A237121, A237594, A239963.

f[k_]:=k^2+1
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,0,Sqrt[Prime[n]-2]}];Print[n," ",m];Continue,{n,1,80}]

ispr(n, p)=my(f=factor(p-1)[, 1], m=Mod(n, p)); for(i=1, #f, if(m^(p\f[i])==1, return(0))); m^(p-1)==1
a(n)=my(p=prime(n)); sum(k=0, sqrtint(p-2), ispr(k^2+1, p)) \\ Charles R Greathouse IV, May 01 2014

A237121 Number of primes p < prime(n)/2 such that P(p) is a primitive root modulo prime(n), where P(.) is the partition function given by A000041.

Original entry on oeis.org

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

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 P(q) = A000041(q) a primitive root modulo p.

			a(14) = 1 since 3 is a prime smaller than prime(14)/2 = 43/2 and P(3) = 3 is a primitive root modulo prime(14) = 43.

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

Cf. A000040, A000041, A236308, A236966, A237112.

f[k_]:=PartitionsP[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,70}]

A239963 Number of triangular numbers below prime(n) which are also primitive roots modulo prime(n).

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Apr 23 2014

nonn

Conjecture: a(n) > 0 for all n > 2. In other words, for any prime p > 3, there is a primitive root 0 < g < p of the form k*(k+1)/2, where k is a positive integer.

			a(5) = 1 since the triangular number 3*4/2 = 6 is a primitive root modulo prime(5) = 11.
a(12) = 1 since the triangular number 5*6/2 = 15 is a primitive root modulo prime(12) = 37.
a(19) = 1 since the triangular number 7*8/2 = 28 is a primitive root modulo prime(19) = 67.

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, A000217, A236308, A236966, A237112, A237121, A237594, A239957.

f[k_]:=f[k]=k(k+1)/2
dv[n_]:=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,(Sqrt[8Prime[n]-7]-1)/2}];Print[n," ",m];Continue,{n,1,80}]

A242248 a(n) = |{0 < g < prime(n): g, 2^g - 1 and (g-1)! are all primitive roots modulo prime(n)}|.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 3, 1, 1, 2, 1, 2, 2, 1, 6, 2, 10, 3, 2, 3, 5, 2, 10, 12, 3, 6, 7, 15, 3, 9, 3, 8, 18, 5, 18, 3, 7, 7, 24, 20, 26, 4, 13, 10, 15, 5, 4, 3, 35, 5, 19, 19, 3, 19, 36, 37, 38, 5, 10, 15, 16, 34, 7, 16, 6, 36, 4, 4, 44, 14

Offset: 1

Zhi-Wei Sun, May 09 2014

nonn

Conjecture: a(n) > 0 for all n > 2. In other words, for any prime p > 3, there exists a positive primitive root g < p modulo p such that 2^g - 1 and (g-1)! are also primitive roots modulo p.

We have verified this for all primes p with 3 < p < 10^6.

			a(4) = 1 since 5, 2^5 - 1 = 31 and (5-1)! = 24 are all primitive roots modulo prime(4) = 7.
a(6) = 1 since 11, 2^(11) - 1 = 2047 and (11-1)! = 3628800 are all primitive roots modulo prime(6) = 13. Note that both 2047 and 3628800 are congruent to 6 modulo 13.
a(14) = 1 since 34, 2^(34) - 1 and (34-1)! are all primititive roots modulo prime(14) = 43. Note that 2^(34) - 1 == 20 (mod 43) and 33! == -14 (mod 43).

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

Cf. A000040, A000142, A000225, A236966, A237112, A242242, A242250.

f[n_]:=2^n-1
g[n_]:=(n-1)!
rMod[m_,n_]:=Mod[m,n,-n/2]
dv[n_]:=Divisors[n]
Do[m=0;Do[If[Mod[f[k],Prime[n]]==0,Goto[aa]];Do[If[Mod[k^(Part[dv[Prime[n]-1],i]),Prime[n]]==1||Mod[rMod[f[k],Prime[n]]^(Part[dv[Prime[n]-1],i]),Prime[n]]==1||Mod[rMod[g[k],Prime[n]]^(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,Prime[n]-1}];Print[n," ",m];Continue,{n,1,70}]

A242250 Least positive integer g < prime(n) such that g, 2^g - 1 and (g-1)! are all primitive roots modulo prime(n), or 0 if such a number g does not exist.

Original entry on oeis.org

1, 0, 3, 5, 8, 11, 5, 13, 21, 10, 12, 22, 24, 34, 13, 31, 18, 6, 41, 11, 14, 53, 8, 6, 26, 3, 12, 5, 47, 10, 45, 10, 5, 32, 12, 6, 24, 3, 15, 3, 6, 41, 19, 10, 8, 30, 3, 67, 5, 35, 20, 13, 99, 19, 7, 7, 3, 118, 5, 15, 22, 3, 73, 59, 91, 8, 137, 46, 20, 55

Offset: 1

Zhi-Wei Sun, May 09 2014

nonn

According to the conjecture in A242248, a(n) should be positive for all n > 2.

			a(5) = 8 since 8, 2^8 - 1 = 255 and (8-1)! = 5040 are all primitive roots modulo prime(5) = 11 with 255 == 5040 == 2 (mod 11), but none of 1, 2^2 - 1, 3, 4, 5, (6-1)! and (7-1)!
is a primitive root modulo 11.

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, A000142, A000225, A236966, A237112, A242242, A242248.

f[n_]:=f[n]=2^n-1
g[n_]:=g[n]=(n-1)!
rMod[m_,n_]:=rMod[m,n]=Mod[m,n,-n/2]
dv[n_]:=dv[n]=Divisors[n]
Do[Do[If[Mod[f[k],Prime[n]]==0,Goto[aa]];Do[If[Mod[k^(Part[dv[Prime[n]-1],i])-1,Prime[n]]==0||Mod[rMod[f[k],Prime[n]]^(Part[dv[Prime[n]-1],i])-1,Prime[n]]==0||Mod[rMod[g[k],Prime[n]]^(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}];Print[n," ",0];Label[bb];Continue,{n,1,70}]

A237594 Number of primes p < prime(n)/2 such that the Bell number B(p) is a primitive root modulo prime(n).

Original entry on oeis.org

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

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 exists a prime q < p/2 such that the Bell number B(q) is a primitive root modulo p.

			a(9) = 1 since 3 is a prime smaller than prime(9)/2 = 23/2 and B(3) = 5 is a primitive root modulo prime(9) = 23.

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

Cf. A000040, A000110, A236308, A236966, A237112, A237121.

f[k_]:=BellB[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}]

cp's OEIS Frontend

A239957 a(n) = |{0 < g < prime(n): g is a primitive root modulo prime(n) of the form k^2 + 1}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A237121 Number of primes p < prime(n)/2 such that P(p) is a primitive root modulo prime(n), where P(.) is the partition function given by A000041.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A239963 Number of triangular numbers below prime(n) which are also primitive roots modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A242248 a(n) = |{0 < g < prime(n): g, 2^g - 1 and (g-1)! are all primitive roots modulo prime(n)}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A242250 Least positive integer g < prime(n) such that g, 2^g - 1 and (g-1)! are all primitive roots modulo prime(n), or 0 if such a number g does not exist.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A237594 Number of primes p < prime(n)/2 such that the Bell number B(p) is a primitive root modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica