A056619 - OEIS

%I #30 Aug 13 2021 19:15:59

%S 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,

%T 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,

%U 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

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

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

%H Robert Israel, <a href="/A056619/b056619.txt">Table of n, a(n) for n = 1..10000</a>

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

%F 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

%p f:= proc(n) local p;

%p    if n::odd then return 2

%p    elif issqr(n) then return 0

%p    fi;

%p    p:= 3;

%p    do

%p       if numtheory:-order(n,p) = p-1 then return p fi;

%p       p:= nextprime(p);

%p    od

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Feb 21 2017

%t 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]]]]];

%t Array[a, 100] (* _Jean-François Alcover_, Apr 10 2019, after _Robert Israel_ *)

%o (PARI) A056619(n)=forprime(p=2,n*2,gcd(n,p)==1&&znorder(Mod(n,p))==p-1&&return(p)) \\ or, more efficient:

%o 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

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

%Y Cf. A001122, A001913, A019334-A019421.

%K nonn

%O 1,1

%A _Robert G. Wilson v_, Aug 07 2000

%E Corrected and extended by _Jud McCranie_, Mar 21 2002

%E Corrected by _Robert Israel_, Feb 21 2017