A060749 -id:A060749 - cp's OEIS frontend

A266986 The indices of primes p for which the average of the primitive roots equals p/2.

1, 3, 6, 7, 8, 10, 12, 13, 16, 18, 21, 24, 25, 26, 29, 30, 33, 35, 37, 40, 42, 44, 45, 50, 51, 53, 55, 57, 59, 60, 62, 63, 65, 66, 68, 70, 71, 74, 77, 78, 79, 80, 82, 84, 87, 88, 89, 97, 98, 100, 102, 104, 106, 108, 110, 112, 113, 116, 119, 121, 122, 123, 126, 127, 130, 134, 135, 136, 137, 139, 140, 142, 145

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

The average of the primitive roots of a prime p are <,=, or > p/2 (observation).
The indices of all primes p==1(mod 4) are in this sequence since for primes of form 4k+1 b a primitive root implies -b a primitive root.
The indices of some primes p==3 (mod 4) are also in this sequence although for most such primes the average of the primitive roots is <> p/2.(observation)

			p(a(1))=p(1)=2. 2 has the primitive root 1. The average primitive root is 1 and 1=2/2.
p(a(2))=p(3)=5. The primitive roots of 5 are 2 and 3. Their average equals (2+3)/phi(4)=5/2=p/2.

Dimitri Papadopoulos, Table of n, a(n) for n = 1..505

Cf. A008330, A060749, A088144, A266987.

A = Table[Total[Flatten[Position[Table[MultiplicativeOrder[i, Prime[k]], {i, Prime[k] - 1}],Prime[k] - 1]]]/(EulerPhi[Prime[k] - 1] Prime[k]/2), {k, 1, 1000}]; Flatten[Position[A, _?(# == 1 &)]]

A266989 Primes for which the average of the primitive roots is < p/2.

Original entry on oeis.org

31, 43, 67, 223, 379, 491, 619, 631, 643, 683, 859, 883, 907, 1051, 1091, 1423, 1747, 1987, 2143, 2347, 2371, 2467, 2531, 2767, 3307, 3643, 3691, 3739, 3823, 3931, 4019, 4219, 4519, 4691, 4987, 5059, 5107, 5347, 5683, 5827, 6043

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

These primes are congruent to 3 (mod 4).

			a(1)=31. The primitive roots of 31 are 3, 11, 12, 13, 17, 21, 22, and 24.
Their average is (3+11+12+13+17+21+22+24)/phi(30)=123/8<31/2.

Robert Israel, Table of n, a(n) for n = 1..1000

Cf. A008330, A060749, A088144, A266987, A266988, A267010.

f:= proc(p) local g;
  if not isprime(p) then return false fi;
  g:= numtheory[primroot](p);
  evalb(add(g&^i mod p, i = select(t->igcd(t,p-1)=1, [$1..p-2]))
     < p/2 * numtheory:-phi(p-1))
end proc:
select(f, [seq(i,i=3..10000,4)]); # Robert Israel, Feb 09 2016

A = Table[Total[Flatten[Position[Table[MultiplicativeOrder[i, Prime[k]], {i, Prime[k] - 1}],Prime[k] - 1]]]/(EulerPhi[Prime[k] - 1] Prime[k]/2), {k, 1,100}]; Prime[Flatten[Position[A, _?(# < 1 &)]]]

ar(p) = my(r, pr, j); r=vector(eulerphi(p-1)); pr=znprimroot(p); for(i=1, p-1, if(gcd(i, p-1)==1, r[j++]=lift(pr^i))); vecsort(r) ;
isok(p) = my(vr = ar(p)); vecsum(vr)/#vr < p/2;
lista(nn) = forprime(p=2, nn, if (isok(p), print1(p, ", "))); \\ Michel Marcus, Feb 09 2016

a(n) = prime(A266988(n)).

A266990 The indices of primes p for which the average of the primitive roots is > p/2.

Original entry on oeis.org

2, 4, 5, 9, 15, 17, 20, 22, 23, 27, 28, 31, 32, 34, 36, 38, 39, 41, 43, 46, 47, 49, 52, 54, 56, 58, 61, 64, 67, 69, 72, 73, 76, 81, 83, 85, 86, 90, 91, 92, 93, 95, 96, 99, 101, 103, 105, 107, 109, 111, 118, 120, 125, 128, 129, 131, 132, 133, 138, 141, 143, 144, 146, 150

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

It appears that these primes are all congruent to 3 (mod 4).

			a(2) = 4 is a term since prime(a(2)) = prime(4) = 7, the primitive roots of 7 are 3 and 5 and their average is (3+5)/2 = 8/2 > 7/2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000720, A008330, A060749, A088144, A267009.

A = Table[Total[Flatten[Position[Table[MultiplicativeOrder[i, Prime[k]], {i, Prime[k] - 1}],Prime[k] - 1]]]/(EulerPhi[Prime[k] - 1] Prime[k]/2), {k, 1, 1000}]; Flatten[Position[A, _?(# > 1 &)]]
Select[Range[150], Mean[PrimitiveRootList[(p = Prime[#])]] > p/2 &] (* Amiram Eldar, Oct 09 2021 *)

a(n) = A000720(A267009(n)). - Amiram Eldar, Oct 09 2021

A267009 Primes p for which the average of the primitive roots is > p/2.

Original entry on oeis.org

3, 7, 11, 23, 47, 59, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 227, 239, 251, 263, 271, 283, 311, 331, 347, 359, 367, 383, 419, 431, 439, 443, 463, 467, 479, 487, 499, 503, 523, 547, 563, 571, 587, 599, 607, 647, 659, 691, 719, 727

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

It appears that these primes are all congruent to 3 (mod 4).

			a(2) = 7 since the primitive roots of 7 are 3 and 5 and their average is (3+5)/2 = 8/2 > 7/2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A008330, A060749, A088144, A266990.

A = Table[Total[Flatten[Position[Table[MultiplicativeOrder[i, Prime[k]], {i, Prime[k] - 1}], Prime[k] - 1]]]/(EulerPhi[Prime[k] - 1] Prime[k]/2), {k, 1, 1000}]; Prime[Flatten[Position[A, _?(# > 1 &)]]]
Select[Range[1000], PrimeQ[#] && Mean[PrimitiveRootList[#]] > #/2 &] (* Amiram Eldar, Oct 09 2021 *)

a(n) = prime(A266990(n)).

A267010 Primes of the form p==3 (mod 4) such that the average of their primitive roots equals p/2.

Original entry on oeis.org

19, 307, 1451, 2179, 2251, 2683, 2843, 3259, 3907, 4447, 11863, 12907, 17623, 30763, 37963, 51059, 52543, 86131, 92467, 104851, 129763, 131203, 146683, 150151, 156151, 156703, 162523, 163819, 174007, 245899, 263827, 287731, 348643, 353611, 400123, 412831, 423091, 432587

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

Most primes for which the average of the primitive roots=p/2 are of the form p==1(mod 4). Much rarer for primes of form p==3(mod 4) to have this property. (Observation)

			19 is a term because the primitive roots of 19 are 2, 3, 10, 13, 14, and 15. Their average is (2+3+10+13+14+15)/phi(18)=57/phi(18)=57/6=19/2.

Cf. A060749. Intersection of A002145 and A266987.

isA267010 := proc(n)
    if isprime(n) and modp(n,4) = 3 then
        isA266987(n) ;
    else
        false;
    end if;
end proc: # R. J. Mathar, Aug 14 2024

f[n_] := If[Total[Flatten[Position[Table[MultiplicativeOrder[i, Prime[n]], {i, Prime[n] - 1}],    Prime[n] - 1]]] == EulerPhi[Prime[n] - 1]*Prime[n]/2, 1, 0];
For[k = 1, k < 10000, k++, If[f[k] == 1 && Mod[Prime[k], 4] == 3, Print[k, "  ", Prime[k]]]]
Select[4*Range[1000] + 3, PrimeQ[#] && Mean[PrimitiveRootList[#]] == #/2 &] (* Amiram Eldar, Oct 11 2021 *)

vr(p) = j=0; r=vector(eulerphi(p-1)); pr=znprimroot(p); for(i=1, p-1, if(gcd(i, p-1)==1, r[j++]=lift(pr^i))); r; \\ after A060749
isok(p) = ((p % 4 == 3) && (vpr = vr(p)) && (vecsum(vpr) == #vpr*p/2)); \\ Michel Marcus, Jan 09 2016

a(16)-a(38) from Michel Marcus, Jan 09 2016

A029932 Primes with record values of the least positive prime primitive root.

Original entry on oeis.org

3, 7, 23, 41, 109, 191, 271, 2791, 11971, 31771, 190321, 2080597, 3545281, 4022911, 73189117, 137568061, 443571241, 565822531, 1160260711, 1622723341, 31552100581, 81651092041, 96736641541, 1867622877121, 5000346134911

Offset: 1

Scott Lindhurst (ScottL(AT)alumni.princeton.edu)

Other terms in the sequence: 39227234631271, 66597722601061 and 84054326426071 -Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 19 2008

Subsequence of A002230, considering only prime primitive roots. - M. F. Hasler, Jun 01 2018

R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, 1961.
A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots. Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968, p. XLV.

Tomás Oliveira e Silva, Counts of least primitive roots of prime numbers (Artin's conjecture)
Tomás Oliveira e Silva, Least prime primitive roots
A. Paszkiewicz and A. Schinzel, On the least prime primitive root modulo a prime, Math. Comp. 71 (2002), no. 239, 1307-1321.
A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots, Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968 [Annotated scans of selected pages]
Index entries for primes by primitive root

Cf. A060749, A002230, A084735.

(* This program is not suitable for computing more than a dozen terms. *) max = 10^8; pprQ[r_, p_] := Union[Table[PowerMod[r, i, p], {i, 1, p+1}]] == coprimes; ppr[p_] := With[{spr = PrimitiveRoot[p]}, If[PrimeQ[spr], spr, coprimes = Select[Range[p-1], CoprimeQ[#, p]&]; For[r = NextPrime[ spr], True, r = NextPrime[r], If[pprQ[r, p], Return[r]]]]]; Reap[ For[ record=1; p=3, p record, record = ppr1; Print["p = ", p, " ppr = ", record]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Feb 25 2016 *)

Corrected by Jud McCranie, Jan 04 2001

2 more terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 19 2008

A138291 Number of primes of the form prime(n)+g, where g is a primitive root of prime(n).

Original entry on oeis.org

1, 1, 1, 0, 3, 1, 3, 1, 2, 4, 2, 2, 4, 3, 2, 7, 10, 3, 3, 3, 4, 6, 10, 7, 6, 11, 7, 12, 7, 9, 6, 10, 14, 10, 17, 10, 10, 12, 11, 13, 22, 7, 9, 11, 16, 10, 5, 13, 23, 8, 23, 12, 9, 23, 26, 22, 25, 13, 12, 14, 13, 19, 12, 18, 14, 32, 17, 18, 30, 22, 32, 21, 20, 14, 17, 28, 30, 19, 19, 21

Offset: 1

T. D. Noe, Mar 12 2008

nonn

It appears that only a(4), corresponding to the prime 7, is zero.

			a(5)=3 because the primitive roots of 11 are 2, 6, 7 and 8. Adding these numbers to 11 produce three primes: 13, 17 and 19.

T. D. Noe, Table of n, a(n) for n=1..2000
Eric Weisstein, MathWorld: Primitive Root

Cf. A047934, A060749 (triangle of primitive roots of primes).

Join[{1}, Table[p=Prime[n]; g=Select[Range[2,p-1], MultiplicativeOrder[ #,p]==p-1&]; Length[Select[p+g, PrimeQ]], {n,2,2000}]]
Table[Count[p+PrimitiveRootList[p],?PrimeQ],{p,Prime[Range[80]]}] (* _Harvey P. Dale, Aug 03 2021 *)

A138327 Nonsquares not representable as p+g, where p is a prime and g is a primitive root of p.

Original entry on oeis.org

2, 6, 11, 14, 26, 35, 41, 45, 51

Offset: 1

T. D. Noe, Mar 14 2008

This is sequence is probably complete.

There are no more terms below 10^5. - Amiram Eldar, Oct 09 2021

Cf. A060749 (primitive roots), A138326.

seq[m_] := Module[{p = Select[Range[m], PrimeQ], s}, s = Complement[Range[m], p + PrimitiveRootList[p] // Flatten]; Select[s, !IntegerQ @ Sqrt[#] &]]; seq[100] (* Amiram Eldar, Oct 09 2021 *)

A138328 Number of ways in which n can be represented as p+g, where p is a prime and g is a primitive root of p.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Mar 14 2008

nonn

T. D. Noe, Table of n, a(n) for n=1..10000

Cf. A060749 (primitive roots), A138325 (least p such that n=p+g).

A242595 a(n) is the primitive period length for the sequence 2^k (mod n), k = 1, 2, ...

Original entry on oeis.org

1, 1, 2, 0, 4, 2, 3, 0, 6, 4, 10, 0, 12, 3, 4, 0, 8, 6, 18, 0, 6, 10, 11, 0, 20, 12, 18, 0, 28, 4, 5, 0, 10, 8, 12, 0, 36, 18, 12, 0, 20, 6, 14, 0, 12, 11, 23, 0, 21, 20, 8, 0, 52, 18, 20, 0, 18, 28, 58, 0, 60, 5, 6, 0, 12, 10, 66, 0, 22, 12, 35, 0, 9, 36, 20, 0, 30, 12, 39, 0, 54, 20, 82, 0, 8, 14, 28, 0

Offset: 1

Wolfdieter Lang, May 18 2014

The computation of this sequence was inspired by Gary Detlefs's May 15 2014 comment on A050229.
It is clear that 2^k (mod 4*m), for k >= 1 is not periodic because otherwise 4*m would divide 2^k*(2^P - 1) for all k >= 1, with P >= 1 the period length. But this is false for k = 1. Therefore, a(4*m) = 0.
a(2*(2*m+1)) = a(2*m+1), m = (0), 1, 2, ... because 2*(2*m+1) has to divide 2^k*(2^a(2*(2*m+1) - 1) for each k >= 1, which means that (2*m+1) has to divide (2^a(2*(2*m+1)) - 1), and a(2*(2*m+1)) has to be the smallest such number. But the smallest number P such that (2*m+1) divides (2^P - 1) is P = a(2*m+1).
a(prime) = phi(prime) = prime - 1 (phi is given in A000010) is equivalent to: prime divides 2^k*(2^(prime-1) - 1), for all k >= 1, and prime-1 is the smallest exponent. For the even prime 2 this is trivial, and for an odd prime p this means that p divides 2^phi(prime) - 1, but not with a smaller exponent; that is 2 is a primitive root modulo this odd p. See A001122 for the primes with primitive root 2. This means that a(prime) = prime - 1 exactly for 2 and the odd primes of A001122. The odd primes with no primitive root 2 are given in A216838.
For composite odd numbers m one has: m divides (2^a(m) - 1) with the smallest such a(m).

			a(1) = 1 because 2^1 == 0 == 1 (mod 1), therefore 2^k (mod 1) is the 0-sequence with primitive period length 1.
a(2) = 1 because 2^k == 0 (mod 2) for k >= 1, hence also the 0-sequence with primitive period length 1. Note that 2 is not a primitive root of 2 even though a(2) = 2-1 = 1 (see the comment above).
a(3) = 3-1 = 2 because 3 is odd and 2 is a primitive root modulo 3. See A001122(1).
a(7) = 3 because the sequence 2^k (mod 7) starts 2, 4, 1, ... therefore the primitive period is 2, 4, 1 of length 3, because 2^(k+3) = 2^k*8 == 2^k*1 (mod 7) == 2^k (mod 7) for all k >= 1. The prime 7 belongs to A216838.
a(4) = 0 because a(4*m) = 0 for all m >= 1 (see the comment above).
a(6) = 2 because the sequence starts with 2, 4, 2, ... and
  6 = 2*3 divides 2^k*(2^2 - 1) = 2^k*3 for all k >= 1. That is a(6) = a(3); see a comment above.
a(9) = 6 from the sequence start 2, 4, 8, 7, 5, 1,... Note that a(3^2) = (3-1)*3. a(5^2) = 20 = (4-1)*5. But a(7^2) = 21 = (7-1)*7/2.

Cf. A000010, A050229, A060749, A001122, A216838.

a(n) is the primitive (smallest) period length of the sequence 2^k (mod n), for k >=1, and n >= 1.

cp's OEIS Frontend

A266986 The indices of primes p for which the average of the primitive roots equals p/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A266989 Primes for which the average of the primitive roots is < p/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A266990 The indices of primes p for which the average of the primitive roots is > p/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A267009 Primes p for which the average of the primitive roots is > p/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A267010 Primes of the form p==3 (mod 4) such that the average of their primitive roots equals p/2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A029932 Primes with record values of the least positive prime primitive root.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A138291 Number of primes of the form prime(n)+g, where g is a primitive root of prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A138327 Nonsquares not representable as p+g, where p is a prime and g is a primitive root of p.