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

Author

Robert G. Wilson v, Aug 07 2000

Keywords

• nonn

Comments

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

Links

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

Crossrefs

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

Cf. A001122, A001913, A019334-A019421.

Programs

Maple

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

Mathematica

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 *)

PARI

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

Formula

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

Extensions

Corrected and extended by Jud McCranie, Mar 21 2002

Corrected by Robert Israel, Feb 21 2017