A001122 -id:A001122 - cp's OEIS frontend

A019338 Primes with primitive root 8.

3, 5, 11, 29, 53, 59, 83, 101, 107, 131, 149, 173, 179, 197, 227, 269, 293, 317, 347, 389, 419, 443, 461, 467, 491, 509, 557, 563, 587, 653, 659, 677, 701, 773, 797, 821, 827, 941, 947, 1019, 1061, 1091, 1109, 1187, 1229, 1259, 1277, 1283, 1301, 1307, 1373, 1427

Offset: 1

David W. Wilson

nonn

To allow primes less than the specified primitive root m (here, 8) 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
Members of A001122 that are not congruent to 1 mod 3. - Robert Israel, Aug 12 2014
Terms greater than 3 are congruent to 5 or 11 modulo 24. - Jianing Song, May 12 2024 [Corrected on May 13 2025]

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

select(t -> isprime(t) and numtheory:-order(8,t) = t-1, [2*i+1 $ i=1..1000]); # Robert Israel, Aug 12 2014

pr=8; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &] (* N. J. A. Sloane, Jun 01 2010 *)
a[p_, q_]:=Sum[2 Cos[2^n Pi/((2 q+1)(2 p+1))],{n,1,2 q p}]
2 Select[Range[800],Rationalize[N[a[#, 3],20]]==1 &]+1
(* Gerry Martens, Apr 28 2015 *)
Join[{3,5},Select[Prime[Range[250]],PrimitiveRoot[#,8]==8&]] (* Harvey P. Dale, Aug 10 2019 *)

is(n)=isprime(n) && n>2 && znorder(Mod(8,n))==n-1 \\ Charles R Greathouse IV, May 21 2015

Let a(p,q)=sum(n=1,2*p*q,2*cos(2^n*Pi/((2*q+1)*(2*p+1)))). Then 2*p+1 is a prime of this sequence when a(p,3)==1. - Gerry Martens, May 15 2015

On Artin's conjecture, a(n) ~ (5/3A) n log n, where A = A005596 is Artin's constant. - Charles R Greathouse IV, May 21 2015

A139035 Primes of the form 4*k+3 with primitive root -2.

Original entry on oeis.org

7, 23, 47, 71, 79, 103, 167, 191, 199, 239, 263, 271, 311, 359, 367, 383, 463, 479, 487, 503, 599, 607, 647, 719, 743, 751, 823, 839, 863, 887, 967, 983, 991, 1031, 1039, 1063, 1087, 1151, 1223, 1231, 1279, 1303, 1319, 1367, 1439, 1447, 1487, 1511, 1543, 1559

Offset: 1

Vladimir Shevelev, May 31 2008, Jun 06 2008

nonn

Original name: Primes with semiprimitive root 2.
If p is a prime, then we call r a semiprimitive root if it has order (p-1)/2 and there is no x for which a^x is congruent to -1 (mod p).  So +/- r^k, 0 <= k <= (p-3)/2 is a complete set of nonzero residues (mod p).
If r=2, then (-1/p)=-1 and, consequently, a(n)==-1(mod 4).
Besides, (2/a(n))=1. Indeed, since 2^((p-1)/2)=1 (mod p), then 2==2^((p+1)/2)=(2^((p+1)/4))^2. Therefore, (a(n))^2==1(mod 16) and thus a(n)==-1(mod 8). This yields that residues 1,2,...,2^((p-3)/2) are quadratic residues modulo a(n), while -1,-2,...,-2^((p-3)/2) are quadratic nonresidues modulo a(n). Primitive root of a(n) is greater than or equal to 3. All terms are in A115591.
Conjecture: primes that have both primitive root -2 and -4. - Davide Rotondo, Dec 20 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
Christian Elsholtz, Almost all primes have a multiple of small Hamming weight, arXiv:1602.05974 [math.NT], 2016. See p. 6.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Vladimir Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.
Vladimir Shevelev Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithm. 136 (2009) 91-100, eq. (10).

Cf. A006694, A002326, A064287, A001917, A001122, A133954, A115591.

Reap[For[p = 3, p <= 10^4, p = NextPrime[p], rp = MultiplicativeOrder[2, p]; rm = MultiplicativeOrder[-2, p]; If[rp != p-1 && rm == p-1, Sow[p]]] ][[2, 1]] (* Jean-François Alcover, Sep 03 2016, after Joerg Arndt *)

{ forprime (p=3, 10^4,
    rp = znorder(Mod(+2,p));
    rm = znorder(Mod(-2,p));
    if ( (rp!=p-1) && (rm==p-1), print1(p,", ") );
);}
/* Joerg Arndt, Jun 03 2012 */

is(n)=n%8==7 && isprime(n) && znorder(Mod(-2,n))==n-1 \\ Charles R Greathouse IV, Nov 30 2017

Prime p is in the sequence iff p==-1(mod 8) and A002326((p-1)/2)=(p-1)/2. A sufficient condition: if p==-1 (mod 8) and (p-1)/2 is prime, then p is in the sequence (the converse statement, generally speaking, is not true).

A006694((a(n)-1)/2)=2 and A064287((a(n)-1)/2)=1.

New name from Joerg Arndt, Jun 03 2012

A167408 Orderly numbers: a number n is orderly if there exists some number k > tau(n) such that the set of the divisors of n is congruent to the set {1,2,...,tau(n)} mod k.

Original entry on oeis.org

1, 2, 5, 7, 8, 9, 11, 12, 13, 17, 19, 20, 23, 27, 29, 31, 37, 38, 41, 43, 47, 52, 53, 57, 58, 59, 61, 67, 68, 71, 72, 73, 76, 79, 83, 87, 89, 97, 101, 103, 107, 109, 113, 117, 118, 124, 127, 131, 133, 137, 139, 149, 151, 157, 158, 162, 163, 164, 167, 173, 177, 178, 179

Offset: 1

Andrew Weimholt, Nov 03 2009

   n: {divisors(n)} == {1,2,...,tau(n)} mod k
  -------------------------------------------
{1} == {1} mod 2
{1,2} == {1,2} mod 3
{1,5} == {1,2} mod 3
{1,7} == {1,2} mod 5
{1,2,8,4} == {1,2,3,4} mod 5
{1,9,3} == {1,2,3} mod 7
{1,11} == {1,2} mod 3 or 9
{1,2,3,4,12,6} == {1,2,3,4,5,6} mod 7
{1,13} == {1,2} mod 11
{1,17} == {1,2} mod 3,5, or 15
{1,19} == 1,2 mod 17
{1,2,10,4,5,20} == {1,2,3,4,5,6} mod 7
{1,23} == {1,2} mod 3,7, or 21
{1,27,3,9} == {1,2,3,4} mod 5
{1,29} == {1,2} mod 3,9, or 27
{1,31} == {1,2} mod 29
{1,37} == 1,2 mod 5,7, or 35
{1,2,38,19} == {1,2,3,4} mod 5
{1,41} == {1,2} mod 3,13, or 39
{1,43} == {1,2} mod 41
{1,47} == {1,2} mod 3,5,9,15, or 45
{1,2,52,4,26,13} == {1,2,3,4,5,6} mod 7
{1,53} == {1,2} mod 3,17, or 51
{1,57,3,19} == {1,2,3,4} mod 5
{1,2,58,29} == {1,2,3,4} mod 5
{1,59} == {1,2} mod 3,19, or 57
{1,61} == {1,2} mod 59
{1,67} == {1,2} mod 5,13, or 65
{1,2,17,4,68,34} == {1,2,3,4,5,6} mod 7
{1,71} == {1,2} mod 3,23, or 69
{1,2,3,4,18,6,72,8,9,36,24,12} == {1,2,3,4,5,6,7,8,9,10,11,12} mod 13
{1,73} == {1,2} mod 71
{1,2,38,4,19,76} == {1,2,3,4,5,6} mod 7
{1,79} == {1,2} mod 7,11, or 77
{1,83} == {1,2} mod 3,9,27, or 81
{1,87,3,29} == {1,2,3,4} mod 5
{1,89} == {1,2} mod 3,29, or 87
{1,97} == {1,2} mod 5,19, or 95
The primes other than 3 are orderly.
Numbers of the form 4p are orderly when p is an odd prime congruent to 3,5, or 6 mod 7.
For primes, k values can be p-2 or a divisor of p-2 other than 1.
T. D. Noe observed that for composite orderly numbers, n, k seems to be one of the three values: tau(n)+1, tau(n)+3, tau(n)+4.
The composite numbers with k = tau(n)+4 are of the form p^2, where prime p == 3 mod 7.
The orderly numbers with k = tau(n)+3 come in many forms. See A168003. It appears that tau(n)+3 is a prime with primitive root 2 (A001122).
The forms for composite orderly numbers with k = tau(n)+1 are too numerous to list here, but seem to occur for any prime k > 3.
Let p be any prime. Then p^(m-2) is in this sequence if m is a prime with primitive root p. For example, 2^(m-2) is here for every m in A001122; 3^(m-2) is here for every m in A019334; 5^(m-2) is here for every m in A019335. For every prime p, there appear to be an infinite number of prime powers p^(m-2) here. All these numbers are actually very orderly (A167409) because we can choose k = tau(n)+1. - T. D. Noe, Nov 04 2009

			12 is an orderly number because 12's divisors are 1,2,3,4,6,12 and
   1 == 1 (mod 7)
   2 == 2 (mod 7)
   3 == 3 (mod 7)
   4 == 4 (mod 7)
  12 == 5 (mod 7)
   6 == 6 (mod 7)

A. Weimholt, Table of n, a(n) for n = 1..10000
Bill McEachen, A167408/A002858

Cf. A167409 = very orderly numbers (k = tau(n) + 1).
Cf. A167410 = disorderly numbers = numbers not in this sequence.
Cf. A167411 = minimal k values for the orderly numbers.

orderlyQ[n_] := (For[dd = Divisors[n]; tau = Length[dd]; k = 3, k <= Max[tau + 4, Last[dd] - 2], k++, If[ Union[ Mod[dd, k]] == Range[tau], Return[True]]]; False); Select[ Range[180], orderlyQ] (* Jean-François Alcover, Aug 19 2013 *)

Minor editing by N. J. A. Sloane, Nov 06 2009

Information about the tau(n)+3 orderly numbers corrected by T. D. Noe, Nov 16 2009

A179383 a(n) = 2*k(n)-1 where k(n) is the sequence of positions of records in A179382.

Original entry on oeis.org

1, 5, 9, 11, 13, 19, 25, 29, 37, 53, 59, 61, 67, 83, 101, 107, 121, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757

Offset: 1

Vladimir Shevelev, Jul 12 2010

nonn

Records in A179382(k(n)) = 1, 2, 3, 5, 6, 9, 10, 14, 18, 26, 29, ....
are located at k(n) = 1, 3, 5, 6, 7, 10, 13, 15, 19, 27, 30, 31,..
The current sequence is a simple transformation of this k(n) sequence.
Question: Are there any terms in the sequence with two or more distinct prime divisors?
Some very plausible conjectures: 1) The sequence consists of primes and squares of primes; 2) The set of squares is finite; 3) A prime p>=5 is in the sequence iff it has primitive root 2 (A001122) ; 4) There exists l such that, for n>l, A179383(n) =A139099(n+l) . [From Vladimir Shevelev , Jul 14 2010]

Peter J. C. Moses, Table of n, a(n) for n = 1..8500

Cf. A139099, A167791, A002326, A179382

Definition rephrased and sequence extended by R. J. Mathar, Jul 13 2010

I made a change to Conjecture 4). - Vladimir Shevelev, Jul 18 2010

A001124 Primes with 5 as smallest primitive root.

Original entry on oeis.org

23, 47, 73, 97, 103, 157, 167, 193, 263, 277, 307, 383, 397, 433, 503, 577, 647, 673, 683, 727, 743, 863, 887, 937, 967, 983, 1033, 1093, 1103, 1153, 1163, 1223, 1367, 1487, 1543, 1583, 1607, 1777, 1823, 1847, 1933, 1993, 2003, 2017, 2063, 2087, 2113, 2203, 2207

Offset: 1

N. J. A. Sloane

nonn

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 864.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 57.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..1000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Index entries for primes by primitive root

Cf. A001122, A001123, A001125, etc.

<< NumberTheory`NumberTheoryFunctions`; Prime[ Select[ Range[200], PrimitiveRoot[ Prime[ # ] ] == 5 & ] ]
(* first load *) << NumberTheory`NumberTheoryFunctions` (* then *) Select[ Prime@Range@300, PrimitiveRoot@# == 5 &] (* Robert G. Wilson v, May 11 2001 *)
Select[Prime[Range[350]],PrimitiveRoot[#]==5&] (* The PrimitiveRoot function is now part of Mathematica's core, so no add-in needs to be loaded before calling it *) (* Harvey P. Dale, Dec 06 2014 *)

from itertools import islice
from sympy import nextprime, primitive_root
def A001124_gen(): # generator of terms
    p = 5
    while (p:=nextprime(p)):
        if primitive_root(p)==5:
            yield p
A001124_list = list(islice(A001124_gen(),30)) # Chai Wah Wu, Feb 13 2023

More terms from Robert G. Wilson v, May 10 2001

A118106 Period of the vector sequence d(n)^k mod n for k=1,2,3,..., where d(n) is the vector of divisors of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 3, 4, 1, 1, 6, 1, 4, 6, 10, 1, 2, 1, 12, 1, 6, 1, 4, 1, 1, 10, 8, 12, 6, 1, 18, 3, 4, 1, 6, 1, 10, 12, 11, 1, 4, 1, 20, 16, 12, 1, 18, 5, 6, 18, 28, 1, 4, 1, 5, 6, 1, 4, 10, 1, 8, 22, 12, 1, 6, 1, 36, 20, 18, 30, 12, 1, 4, 1, 20, 1, 6, 16, 14, 28, 10, 1, 12, 12

Offset: 1

T. D. Noe, Apr 13 2006

nonn

This sequence is related to the period of sigma_k(n) mod n. Note that a(n)=1 iff n is a power of a prime.
The record periods of p-1 occur at n=2p, where p is a prime with primitive root 2 (A001122). - T. D. Noe, Oct 25 2007
From Jianing Song, Nov 03 2019: (Start)
The smallest index m such that from the m-th term on, the sequence {d(n)^k mod n: k >= 0} enters into a cycle is m = A051903(n).
Let b(n) be the period of {sigma_k(n) mod n: k >= 0}, then b(n) | a(n) for all n, but generally they are not necessarily the same (for example, a(576) = 48 while b(576) = 16).
Every number m occurs in this sequence. Suppose m != 1, 6, by Zsigmondy's theorem, 2^m - 1 has at least one primitive factor p. Here a primitive factor p means that ord(2,p) = m. So we have a(2p) = lcm(ord(2,p), ord(p,2)) = m (see the formula below). Specially, we have a(2*A112927(m)) = a(2*A097406(m)) = m for m != 1, 6. (End)

			a(35)=12 because d(35)=(1,5,7,35) and (1,5,7,35)^k (mod 35) is the sequence of vectors (1,5,7,0), (1,25,14,0), (1,20,28,0), (1,30,21,0), (1,10,7,0), (1,15,14,0), (1,5,28,0), (1,25,21,0), (1,20,7,0), (1,30,14,0), (1,10,28,0), (1,15,21,0), (1,5,7,0),..., which has a period of 12.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..1000 from T. D. Noe)

Cf. A118107 (period of the vector sequence d(n)^2^k mod n), A051903.

Table[d=Divisors[n]; k=0; found=False; While[i=0; While[i

A118106(n) = { my(divs=apply(d -> (d%n),divisors(n)), odivs = Vec(divs), vs = Map()); mapput(vs, odivs, 0); for(k=1,oo,divs = vector(#divs,i,(divs[i]*odivs[i])%n); if(mapisdefined(vs, divs), return(k-mapget(vs, divs)), mapput(vs, divs, k))); }; \\ Antti Karttunen, Sep 23 2018

a(n) = my(m=omega(n), M=vector(m^2),f=factor(n)); for(i=1, m, for(j=1, m, M[(i-1)*m+j]=if(i==j, 1, znorder(Mod(f[i,1],f[j,1]^f[j,2]))))); lcm(M) \\ Jianing Song, Nov 03 2019

Write n = Product_{i=1..t} p_i^e_i, then a(n) = lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j), where ord(a,r) is the multiplicative order of a modulo r. - Jianing Song, Nov 03 2019

A212953 Minimal order of degree-n irreducible polynomials over GF(2).

Original entry on oeis.org

1, 3, 7, 5, 31, 9, 127, 17, 73, 11, 23, 13, 8191, 43, 151, 257, 131071, 19, 524287, 25, 49, 69, 47, 119, 601, 2731, 262657, 29, 233, 77, 2147483647, 65537, 161, 43691, 71, 37, 223, 174763, 79, 187, 13367, 147, 431, 115, 631, 141, 2351, 97, 4432676798593, 251

Offset: 1

Alois P. Heinz, Jun 01 2012

nonn

a(n) = smallest odd m such that A002326((m-1)/2) = n. - Thomas Ordowski, Feb 04 2014

For n > 1; n < a(n) < 2^n, wherein a(n) = n+1 iff n+1 is A001122 a prime with primitive root 2, or a(n) = 2^n-1 iff n is a Mersenne exponent A000043. - Thomas Ordowski, Feb 08 2014

			For n=4 the degree-4 irreducible polynomials p over GF(2) are 1+x+x^2+x^3+x^4, 1+x+x^4, 1+x^3+x^4. Their orders (i.e., the smallest integer e for which p divides x^e+1) are 5, 15, 15. (Example: (1+x+x^2+x^3+x^4) * (1+x) == x^5+1 (mod 2)). Thus the minimal order is 5 and a(4) = 5.

W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers, Springer 2004, Third Edition, 4.3 Factorization of Prime Ideals in Extensions. More About the Class Group (Theorem 4.33), 4.4 Notes to Chapter 4 (Theorem 4.40). - Regarding the first comment.

Max Alekseyev, Table of n, a(n) for n = 1..1236 (first 179 terms from Alois P. Heinz)
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Polynomial Order

Cf. A003060, A059912, A213224.

with(numtheory):
M:= proc(n) option remember;
      divisors(2^n-1) minus U(n-1)
    end:
U:= proc(n) option remember;
      `if`(n=0, {}, M(n) union U(n-1))
    end:
a:= n-> min(M(n)[]):
seq(a(n), n=1..50);

M[n_] := M[n] = Divisors[2^n-1] ~Complement~ U[n-1];
U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n-1]];
a[n_] := Min[M[n]];
Array[a, 50] (* Jean-François Alcover, Mar 22 2017, translated from Maple *)

a(n) = min(M(n)) with M(n) = {d : d|(2^n-1)} \ U(n-1) and U(n) = M(n) union U(n-1) for n>0, U(0) = {}.

a(n) = A059912(n,1) = A213224(n,1).

A268923 All odd primes a(n) such that for all odd primes q smaller than a(n) the order of 2 modulo a(n)q is a proper divisor of phi(a(n)q)/2. The totient function phi is given in A000010.

Original entry on oeis.org

17, 31, 41, 43, 73, 89, 97, 109, 113, 127, 137, 151, 157, 193, 223, 229, 233, 241, 251, 257, 277, 281, 283, 307, 313, 331, 337, 353, 397, 401, 409, 431, 433, 439, 449, 457, 499, 521, 569, 571, 577, 593, 601, 617, 631, 641, 643, 673, 683, 691, 727, 733, 739, 761, 769, 809, 811, 857, 881, 911, 919

Offset: 1

Wolfdieter Lang, Apr 01 2016

nonn

This sequence was inspired by A269454 submitted by Marina Ibrishimova.
It seems that if for an odd prime p > 3 the order(2, p*3) < phi(p*3)/2 = p-1 then p is in this sequence.
Note that 2^(phi(p*q)/2) == 1 (mod p*q) for distinct odd primes p and q, due to Nagell's corollary on Theorem 64, p. 106. The products of distinct primes considered in the present sequence have order of 2 modulo p*q smaller than phi(p*q)/2.
Up to and including prime(100) = 541 the only odd primes p such that for all odd primes q smaller than p the order of 2 modulo p*q equals phi(p*q)/2 are 5, 7, and 11.
Complement of A216371 = A001122 U A105874 in the set of odd primes. Composed of the primes modulo which neither 2 nor -2 is a primitive root. Also, prime(n) is a term iff A376010(n) > 2. - Max Alekseyev, Sep 05 2024

			n=1: Order(2, 17*3) = 8, and 8 is a proper divisor of phi(17*3)/2 = 16;
   order(2, 17*5) =  8, and 8 is a proper divisor of phi(17*5)/2 = 32;
   order(2, 17*7) = 24, and 24 is a proper divisor of phi(17*7)/2 = 48;
   order(2, 17*11) = 40, and 40 is a proper divisor of phi(17*11)/2 = 80;
   order(2, 17*13) = 24, and 24 is a proper divisor of phi(17*13)/2 = 96.

Michael De Vlieger, Table of n, a(n) for n = 1..1000
Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.

Cf. A000010, A002326, A001122, A105874, A216371, A269454, A376010.

Select[Prime@ Range[3, 157], Function[p, AllTrue[Prime@ Range[2, PrimePi@ p - 1], Function[q, With[{e = EulerPhi[p q]/2}, And[Divisible[e, #], # != e]] &@ MultiplicativeOrder[2, p q]]]]] (* Michael De Vlieger, Apr 01 2016, Version 10 *)

More terms from Michael De Vlieger, Apr 01 2016

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

Original entry on oeis.org

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

A066529 a(n) is the least index such that the least primitive root of the a(n)-th prime is n, or zero if no such prime exists.

Original entry on oeis.org

1, 2, 4, 0, 9, 13, 20, 0, 0, 65, 117, 566, 88, 173, 85, 0, 64, 5426, 43, 10217, 80, 474, 326, 44110, 0, 1479, 0, 12443, 1842, 11662, 775, 0, 23559, 5029, 6461, 0, 3894, 5629, 15177, 105242, 14401, 182683, 9204, 7103, 5518399, 23888, 24092, 42304997, 0, 1455704, 27848, 12107, 14837, 205691645, 38451, 12102037, 39370, 28902, 57481, 56379, 90901, 53468, 5918705, 0, 732055, 1738826, 242495, 265666, 10523, 388487, 260680

Offset: 1

Wouter Meeussen, Jan 06 2002

nonn

The corresponding primes are in A023048.

For n < 150, only a(108) is presently unknown. - Robert G. Wilson v, Jan 03 2006

			a(6) = 13 because Prime[13] = 41 is the least prime with least primitive root = 6

Tomás Oliveira e Silva, Least prime primitive root of prime numbers
E. Weisstein, Primitive Roots
Index entries for primes by primitive root

Cf. A001918, A001122, A001123, A023048, A001597.

big = Table[ p = Prime[ n ]; PrimitiveRoot[ p ], {n, 1, 1000000} ]; Flatten[ Table[ Position[ big, n, 1, 1 ]/.{}-> 0, {n, 79} ] ] (* First load package NumberTheory`NumberTheoryFunctions` *)
(* first load package *) << NumberTheory`NumberTheoryFunctions` (* then do *) t = Table[0, {100}]; Do[a = PrimitiveRoot@Prime@n; If[a < 101 && t[[a]] == 0, t[[a]] = n], {n, 10^6}]; t (* Robert G. Wilson v, Dec 15 2005 *)

a(n) = 0 iff n is a perfect power (A001597) > 1. - Robert G. Wilson v, Jan 03 2006

a(n) = min { k | A001918(k) = n } U {0} = A000720(A023048(n)) (or zero). - M. F. Hasler, Jun 01 2018

Edited by Dean Hickerson, Jan 14 2002

Further terms from Robert G. Wilson v, Jan 03 2006

cp's OEIS Frontend

A019338 Primes with primitive root 8.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

PARI

Formula

A139035 Primes of the form 4*k+3 with primitive root -2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A167408 Orderly numbers: a number n is orderly if there exists some number k > tau(n) such that the set of the divisors of n is congruent to the set {1,2,...,tau(n)} mod k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A179383 a(n) = 2*k(n)-1 where k(n) is the sequence of positions of records in A179382.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A001124 Primes with 5 as smallest primitive root.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A118106 Period of the vector sequence d(n)^k mod n for k=1,2,3,..., where d(n) is the vector of divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A212953 Minimal order of degree-n irreducible polynomials over GF(2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A268923 All odd primes a(n) such that for all odd primes q smaller than a(n) the order of 2 modulo a(n)q is a proper divisor of phi(a(n)q)/2. The totient function phi is given in A000010.