A242250 -id:A242250 - cp's OEIS frontend

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

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

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

A242266 a(n) = |{0 < g < prime(n): g is a primitive root mod prime(n) with g = sum_{j=1..k} prime(j) for some k > 0}|.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 2, 3, 2, 1, 3, 2, 2, 3, 3, 2, 3, 3, 1, 3, 2, 3, 3, 5, 2, 2, 6, 2, 4, 1, 3, 2, 3, 5, 2, 2, 2, 6, 6, 6, 7, 2, 6, 4, 4, 4, 5, 6, 5, 6, 3, 1, 3, 7, 9, 9, 2, 5, 2, 2, 6, 4, 5, 6, 6, 4, 3, 8, 3, 6, 6, 7, 5, 6, 9, 8, 6, 4, 4

Offset: 1

Zhi-Wei Sun, May 09 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 1. In other words, for any odd prime p, there is a positive integer k such that the sum of the first k primes is not only a primitive root modulo p but also smaller than p.
(ii) For any n > 1, there is a number k among 1, ..., n such that sum_{j=1..k}(-1)^(k-j)*prime(j) is a primitive root modulo prime(n).
We have verified parts (i) and (ii) for n up to 700000 and 250000 respectively. Note that prime(700000) > 10^7.

			a(4) = 1 since prime(1) + prime(2) = 2 + 3 = 5 is a primitive root modulo prime(4) = 7 with 5 < 7.
a(7) = 2 since prime(1) = 2 and prime(1) + prime(2) + prime(3) = 2 + 3 + 5 = 10 are not only primitive roots modulo prime(7) = 17 but also smaller than 17.
a(53) = 1 since sum_{j=1..10} prime(j) = 129 is a primitive root modulo prime(53) = 241 with 129 < 241.

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, A008347, A007504, A236966, A239957, A241476, A241504, A241516, A242248, A242250, A242277.

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

cp's OEIS Frontend

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

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

A242266 a(n) = |{0 < g < prime(n): g is a primitive root mod prime(n) with g = sum_{j=1..k} prime(j) for some k > 0}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica