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,1

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

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

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

Prog

(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

Crossrefs

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

Cf. A001122, A001913, A019334-A019421.

Sequence in context: A269735 A187038 A332260 * A324300 A323695 A303121

Adjacent sequences: A056616 A056617 A056618 * A056620 A056621 A056622

Keyword

nonn

Author

Robert G. Wilson v, Aug 07 2000

Extensions

Corrected and extended by Jud McCranie, Mar 21 2002

Corrected by Robert Israel, Feb 21 2017

Status

approved