A023049 -id:A023049 - 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

A377938 a(n) is the least k > n such that n is a primitive root modulo k, or -1 if there is no such k.

Original entry on oeis.org

2, 3, 4, -1, 6, 11, 10, 11, -1, 17, 13, 17, 19, 17, 19, -1, 22, 29, 22, 23, 23, 25, 25, 31, -1, 29, 29, 41, 34, 41, 34, 37, 38, 41, 37, -1, 46, 47, 47, 47, 47, 59, 46, 47, 47, 67, 49, 53, -1, 53, 53, 59, 62, 59, 58, 59, 67, 73, 61, 73, 67, 71, 67, -1, 71, 79, 71, 71, 71, 79, 82, 83, 83, 79, 79

Offset: 1

Robert Israel, Nov 11 2024

sign

a(n) <= A023049(n).

a(n) = 0 iff n is a square > 1.

			a(6) = 11 because 6 is a primitive root mod 11 and no number from 7 to 10 has 6 as a primitive root.

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

Cf. A023049, A377939. A377940.

N:= 1000: # to allow values <= N
P:= select(isprime, {seq(i,i=3..N,2)}):
Cands:= map(proc(t) local i; (seq(t^i,i=1..ilog[t](N)), seq(2*t^i,i=1..ilog[t](N/2))) end proc,P):
Cands:= sort(convert({4} union Cands, list)):
Phis:= map(numtheory:-phi, Cands):
f:= proc(n)
local k0,k;
      if issqr(n) then return -1 fi;
      k0:= ListTools:-BinaryPlace(Cands,n)+1;
      for k from k0 do
        if igcd(Cands[k],n) = 1 and numtheory:-order(n,Cands[k]) = Phis[k] then return Cands[k] fi
      od
end proc:
f(1):= 2:
map(f, [$1..200]);

A377939 Nonsquares k such that A377938(k) is not a prime.

Original entry on oeis.org

3, 5, 7, 17, 19, 22, 23, 29, 31, 33, 37, 43, 47, 53, 55, 71, 85, 87, 89, 91, 102, 103, 105, 106, 109, 111, 112, 113, 115, 116, 117, 122, 123, 133, 139, 141, 143, 145, 149, 153, 155, 157, 162, 163, 167, 175, 177, 191, 193, 199, 201, 203, 209, 211, 221, 223, 233, 239, 241, 243, 245, 247, 249, 253

Offset: 1

Robert Israel, Nov 11 2024

nonn

Numbers k such that k is a primitive root modulo some nonprime x > k but not modulo any prime between k and x.

Numbers k such that 0 < A377938(k) < A023049(k).

			a(3) = 7 is a term because 7 is a primitive root mod 10, while the least prime > 7 for which 7 is a primitive root is 11.

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

Cf. A023049, A377938.

filter:= proc(n) local k;
  if issqr(n) then return false fi;
  for k from n+1 do
    if igcd(k,n) = 1 and numtheory:-order(n,k) = numtheory:-phi(k) then return not isprime(k) fi
  od
end proc:
select(filter, [$2..1000]);

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

A377938 a(n) is the least k > n such that n is a primitive root modulo k, or -1 if there is no such k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A377939 Nonsquares k such that A377938(k) is not a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple