A019334 -id:A019334 - cp's OEIS frontend

A056619 Smallest prime with primitive root n, or 0 if no such prime exists.

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, 13, 2, 5, 2, 3, 2, 5, 2, 11, 2, 3, 2, 5, 2, 11, 2, 3, 2, 7, 2, 7, 2, 3, 2

Offset: 1

Robert G. Wilson v, Aug 07 2000

nonn

a(n) > n/2 for n in { 2, 6, 10, 34 }. Are there any other such indices n? - M. F. Hasler, Feb 21 2017

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

Here the primitive root may be larger than the prime, whereas in A023049 it may not be.

Cf. A001122, A001913, A019334-A019421.

f:= proc(n) local p;
   if n::odd then return 2
   elif issqr(n) then return 0
   fi;
   p:= 3;
   do
      if numtheory:-order(n,p) = p-1 then return p fi;
      p:= nextprime(p);
   od
end proc:
map(f, [$1..100]); # Robert Israel, Feb 21 2017

a[n_] := Module[{p}, If[OddQ[n], Return[2], If[IntegerQ[Sqrt[n]], Return[0], p = 3; While[True, If[MultiplicativeOrder[n, p] == p-1, Return[p]]; p = NextPrime[p]]]]];
Array[a, 100] (* Jean-François Alcover, Apr 10 2019, after Robert Israel *)

A056619(n)=forprime(p=2,n*2,gcd(n,p)==1&&znorder(Mod(n,p))==p-1&&return(p)) \\ or, more efficient:
A056619(n)=if(bittest(n,0),2,!issquare(n)&&forprime(p=3,n*2,gcd(n,p)==1&&znorder(Mod(n,p))==p-1&&return(p))) \\ M. F. Hasler, Feb 21 2017

a(n) = 0 only for perfect squares, A000290.

a(n) = 2 for all odd n. a(n) = 0 for even squares. a(n) = 3 for n = 2 (mod 6). a(n) = 5 for n in {12, 18, 22, 28} (mod 30). - M. F. Hasler, Feb 21 2017

Corrected and extended by Jud McCranie, Mar 21 2002

Corrected by Robert Israel, Feb 21 2017

A109641 Composite n such that binomial(3n, n) == 3^k (mod n) for some integer k > 0.

Original entry on oeis.org

4, 9, 15, 25, 27, 34, 36, 49, 51, 57, 63, 68, 75, 81, 87, 93, 111, 121, 125, 129, 132, 138, 141, 153, 155, 159, 169, 177, 237, 249, 258, 261, 264, 267, 274, 276, 279, 289, 298, 303, 324, 339, 343, 357, 361, 375, 381, 387, 393, 411, 417, 423, 441, 447, 453, 477

Offset: 1

Ryan Propper, Aug 05 2005

nonn

Includes p^k for k >= 2 and p > 2 in A019334 but not in A014127, as binomial(3n,n) is coprime to p and 3 is a primitive root mod p^k. - Robert Israel, Nov 12 2017

			Binomial(3*34,34) == 3^6 (mod 34), so 34 is a member.

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

Cf. A019334, A080469, A014127, A109642.

filter:= proc(n) local p,m,k,t;
  if isprime(n) then return false fi;
  p:= padic:-ordp(n,3);
  p:= p + numtheory:-order(3, n/3^p);
  m:= binomial(3*n,n) mod n;
  t:= 1;
  for k from 1 to p do
    t:= t*3 mod n;
    if t = m then return true fi;
  od:
false
end proc;
select(filter, [$2..1000]); # Robert Israel, Nov 12 2017

okQ[n_] := Module[{p, m}, If[PrimeQ[n], Return[False]]; p = IntegerExponent[n, 3]; p = p + MultiplicativeOrder[3, n/3^p]; m = Mod[Binomial[3n, n], n]; AnyTrue[Range[p], m == PowerMod[3, #, n]&]];
Select[Range[2, 500], okQ] (* Jean-François Alcover, Mar 27 2019, after Robert Israel *)

Corrected and extended by Max Alekseyev, Sep 13 2009

Edited by Max Alekseyev, Sep 20 2009

A019336 Primes with primitive root 6.

Original entry on oeis.org

11, 13, 17, 41, 59, 61, 79, 83, 89, 103, 107, 109, 113, 127, 131, 137, 151, 157, 179, 199, 223, 227, 229, 233, 251, 257, 271, 277, 347, 367, 373, 397, 401, 419, 443, 449, 467, 487, 491, 521, 563, 569, 587, 593, 613, 641, 659, 661, 683, 709, 733, 757, 761, 809, 823, 827

Offset: 1

David W. Wilson

nonn

To allow primes less than the specified primitive root m (here, 6) to be included, we use the essentially equivalent definition "Primes p such that the multiplicative order of m mod p is p-1". This comment applies to all of A019334-A019421. - N. J. A. Sloane, Dec 03 2019

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for primes by primitive root

pr=6; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &]

A217520 Base-3 state complexity of partitioned deterministic finite automaton (PDFA) for the periodic sequence (123...n)*.

Original entry on oeis.org

2, 4, 8, 20, 7, 42, 16, 13, 40, 55, 25, 39, 84, 61, 64, 272, 22, 342, 80, 127, 110, 253, 49, 500, 78, 40, 168, 812, 121, 930, 256, 166, 544, 420, 76, 666, 684, 118, 160, 328, 253, 1806, 440, 184, 506, 1081, 193, 2058, 1000, 817, 312, 2756, 67

Offset: 2

N. J. A. Sloane, Oct 07 2012

nonn

Also the number of distinct words that can be formed from (123..n)* by taking every 3^k-th term from some initial index i, with i and k nonnegative. (Follows from Case 2 of Theorem 2.1) - Charlie Neder, Feb 28 2019

Charlie Neder, Table of n, a(n) for n = 2..100
Klaus Sutner and Sam Tetruashvili, Inferring Automatic Sequences.

Cf. A217519, A217521, A247566-A247581, A019334.

a(3^k) = (3^(k+1)-1)/2. It appears that a(n) <= n(n-1), with equality if and only if n is a prime with primitive root 3 (A019334). - Charlie Neder, Feb 28 2019

a(11)-a(20) added (see Inferring Automatic Sequences) by Vincenzo Librandi, Nov 18 2012

a(21)-a(54) from Charlie Neder, Feb 28 2019

A222008 Primes of the form 4^k + 1 for some k > 0.

Original entry on oeis.org

5, 17, 257, 65537

Offset: 1

Jonathan Sondow, Feb 04 2013

nonn

Same as Fermat primes 2^(2^m) + 1 for m >= 1. See A019434 for comments, etc.
Chebyshev showed that 3 is a primitive root of all primes of the form 2^(2*k) + 1 with k > 0. If the sequence is infinite, then Artin's conjecture ("every nonsquare integer n != -1 is a primitive root of infinitely many primes q") is true for n = 3.
As a(n) is a Fermat prime > 3, by Pépin's test a(n) has primitive root 3.
Conjecture: let p a prime number, a(n) is not congruent to p mod (p^2-3)/2. - Vincenzo Librandi, Jun 15 2014
This conjecture is false when p = a(n), but may be true for primes p != a(n). - Jonathan Sondow, Jun 15 2014
Primes p with the property that k-th smallest divisor of its squares p^2, for all 1 <= k <= tau(p^2), contains exactly k "1" digits in its binary representation. Corresponding values of squares p^2: 25, 289, 66049, 4295098369. Example: p = 257, set of divisors of p^2 = 66049 in binary representation: {1, 100000001, 10000001000000001}. Subsequence of A255401. - Jaroslav Krizek, Dec 21 2016

			4^1 + 1 = 5 is prime, so a(1) = 5. Also, 3^k == 3, 4, 2, 1 (mod 5) for k = 1, 2, 3, 4, resp., so 3 is a primitive root for a(1).

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966, p. 102, nr. 3.
P. L. Chebyshev, Theory of congruences. Elements of number theory, Chelsea, 1972, p. 306.

P. L. Chebyshev, Theorie der Congruenzen, Mayer & Mueller, 1889, p. 306-313.
R. Fueter, Über primitive Wurzeln von Primzahlen, Comment. Math. Helv., 18 (1946), 217-223, p. 217.
Wikipedia, Pépin's test
Index entries for sequences related to Artin's conjecture
Index entries for primes by primitive root

Cf. A005596, A019334, A019434, A090866, A221981.

Select[Table[4^k + 1, {k, 10^3}], PrimeQ] (* Michael De Vlieger, Dec 22 2016 *)

a(n) = A019434(n+1) for n > 0.

A323594 Primes p such that 3 is a primitive root modulo p while 27 is not.

Original entry on oeis.org

7, 19, 31, 43, 79, 127, 139, 163, 199, 211, 223, 283, 331, 379, 463, 487, 571, 607, 631, 691, 739, 751, 811, 823, 859, 907, 1039, 1063, 1087, 1123, 1231, 1279, 1291, 1327, 1423, 1447, 1459, 1483, 1567, 1579, 1627, 1663, 1699, 1723, 1747, 1831, 1951, 1987, 1999

Offset: 1

Jianing Song, Aug 30 2019

nonn

Primes p such that 3 is a primitive root modulo p (i.e., p is in A019334) and that p == 1 (mod 3).

According to Artin's conjecture, the number of terms <= N is roughly ((2/5)*C)*PrimePi(N), where C is the Artin's constant = A005596, PrimePi = A000720. Compare: the number of terms of A001122 that are no greater than N is roughly C*PrimePi(N).

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Artin's constant.
Wikipedia, Artin's conjecture on primitive roots.

Complement of A019353 with respect to A019334.
Cf. also A005596, A000720.
Primes p such that 3 is a primitive root modulo p and that p == 1 (mod q): this sequence (q=3), A323617 (q=5), A323628 (q=7).

forprime(p=5, 2000, if(znorder(Mod(3, p))==(p-1) && p%3==1, print1(p, ", ")))

A364867 Primes p such that the multiplicative order of 9 modulo p is (p-1)/2.

Original entry on oeis.org

5, 7, 11, 17, 19, 23, 29, 31, 43, 47, 53, 59, 71, 79, 83, 89, 101, 107, 113, 127, 131, 137, 139, 149, 163, 167, 173, 179, 191, 197, 199, 211, 223, 227, 233, 239, 251, 257, 263, 269, 281, 283, 293, 311, 317, 331, 347, 353, 359, 379, 383, 389, 401, 419, 443, 449, 461, 463, 467, 479, 487

Offset: 1

Jianing Song, Aug 11 2023

Primes p such that the multiplicative order of 9 modulo p is of the maximum possible value.
Primes p such that 3 or -3 (or both) is a primitive root modulo p. Proof of equivalence: let ord(a,k) be the multiplicative order of a modulo p. if ord(3,p) = p-1, then clearly ord(9,p) = (p-1)/2. If ord(-3,p) = p-1, then we also have ord(9,p) = (p-1)/2. Conversely, suppose that ord(9,p) = (p-1)/2, then ord(3,p) = p-1 or (p-1)/2, and ord(-3,p) = p-1 or (p-1)/2. If ord(3,p) = ord(-3,p) = (p-1)/2, then we have that (p-1)/2 is odd and (-1)^((p-1)/2) == 1 (mod p), a contradiction.
A prime p is a term if and only if one of the two following conditions holds: (a) 3 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of 3 modulo p is (p-1)/2 (in this case, we have p == 11 (mod 12) since 3 is a quadratic residue modulo p).
A prime p is a term if and only if one of the two following conditions holds: (a) -3 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of -3 modulo p is (p-1)/2 (in this case, we have p == 7 (mod 12) since -3 is a quadratic residue modulo p).
No terms are congruent to 1 modulo 12, since otherwise we would have 9^((p-1)/4) = (+-3)^((p-1)/2) == 1 (mod p). - Jianing Song, May 14 2024

			7 is a term since the multiplicative order of 9 modulo 7 is 3 = (7-1)/2.

Jianing Song, Table of n, a(n) for n = 1..10000

Union of A019334 and A105875.
A105881 is the subsequence of terms congruent to 3 modulo 4.
Cf. A211245 (order of 9 mod n-th prime), A216371.

okQ[p_] := MultiplicativeOrder[9, p] == (p - 1)/2;
Select[Prime[Range[100]], okQ] (* Jean-François Alcover, Nov 24 2024 *)

isA364867(p) = isprime(p) && (p!=3) && znorder(Mod(9, p)) == (p-1)/2

from sympy import n_order, nextprime
from itertools import islice
def A364867_gen(startvalue=4): # generator of terms >= startvalue
    p = max(startvalue-1,3)
    while (p:=nextprime(p)):
        if n_order(9,p) == p-1>>1:
            yield p
A364867_list = list(islice(A364867_gen(),20)) # Chai Wah Wu, Aug 11 2023

A019340 Primes with primitive root 12.

Original entry on oeis.org

5, 7, 17, 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 223, 257, 269, 281, 283, 293, 317, 353, 367, 379, 389, 401, 449, 461, 509, 523, 547, 557, 569, 571, 593, 607, 617, 619, 631, 641, 653, 691, 701, 739, 751, 761, 773, 787, 797, 809, 821

Offset: 1

David W. Wilson

To allow primes less than the specified primitive root m (here, 12) to be included, we use the essentially equivalent definition "Primes p such that the multiplicative order of m mod p is p-1". This comment applies to all of A019334-A019421. - N. J. A. Sloane, Dec 03 2019

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for primes by primitive root

pr=12; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &]

A323617 Primes p such that 3 is a primitive root modulo p while 243 is not.

Original entry on oeis.org

31, 101, 211, 281, 331, 401, 461, 521, 571, 631, 641, 691, 701, 751, 811, 821, 881, 941, 1061, 1231, 1291, 1301, 1361, 1481, 1601, 1721, 1831, 1901, 1951, 2011, 2081, 2141, 2311, 2371, 2381, 2731, 2741, 2801, 2861, 3041, 3271, 3331, 3391, 3461, 3571, 3581, 3701, 3761, 3821, 3931

Offset: 1

Jianing Song, Aug 30 2019

nonn

Primes p such that 3 is a primitive root modulo p (i.e., p is in A019334) and that p == 1 (mod 5).

According to Artin's conjecture, the number of terms <= N is roughly ((4/19)*C)*PrimePi(N), where C is the Artin's constant = A005596, PrimePi = A000720. Compare: the number of terms of A001122 that are no greater than N is roughly C*PrimePi(N).

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Artin's constant.
Wikipedia, Artin's conjecture on primitive roots.

Cf. A019334, A005596, A000720.

Primes p such that 3 is a primitive root modulo p and that p == 1 (mod q): A323594 (q=3), this sequence (q=5), A323628 (q=7).

forprime(p=5, 4000, if(znorder(Mod(3, p))==(p-1) && p%5==1, print1(p, ", ")))

A323628 Primes p such that 3 is a primitive root modulo p while 2187 is not.

Original entry on oeis.org

29, 43, 113, 127, 197, 211, 281, 379, 449, 463, 617, 631, 701, 953, 1373, 1709, 1723, 2129, 2143, 2213, 2311, 2381, 2549, 2633, 2647, 2731, 2801, 2969, 3137, 3389, 3557, 3571, 3823, 4159, 4229, 4243, 4327, 4397, 4481, 4649, 4663, 4817, 4831, 4999, 5237, 5419

Offset: 1

Jianing Song, Aug 30 2019

nonn

Primes p such that 3 is a primitive root modulo p (i.e., p is in A019334) and that p == 1 (mod 7).

According to Artin's conjecture, the number of terms <= N is roughly ((6/41)*C)*PrimePi(N), where C is the Artin's constant = A005596, PrimePi = A000720. Compare: the number of terms of A001122 that are no greater than N is roughly C*PrimePi(N).

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Artin's constant
Wikipedia, Artin's conjecture on primitive roots

Cf. A019334, A005596, A000720.

Primes p such that 3 is a primitive root modulo p and that p == 1 (mod q): A323594 (q=3), A323617 (q=5), this sequence (q=7).

select(p -> isprime(p) and numtheory:-order(3,p)=p-1, [seq(i,i=1..10000,7)]); # Robert Israel, Sep 01 2019

forprime(p=5, 5500, if(znorder(Mod(3, p))==(p-1) && p%7==1, print1(p, ", ")))

cp's OEIS Frontend

A056619 Smallest prime with primitive root n, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A109641 Composite n such that binomial(3n, n) == 3^k (mod n) for some integer k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A019336 Primes with primitive root 6.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

A217520 Base-3 state complexity of partitioned deterministic finite automaton (PDFA) for the periodic sequence (123...n)*.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A222008 Primes of the form 4^k + 1 for some k > 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A323594 Primes p such that 3 is a primitive root modulo p while 27 is not.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A364867 Primes p such that the multiplicative order of 9 modulo p is (p-1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A019340 Primes with primitive root 12.

Views

Author

Keywords