cp's OEIS Frontend

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

%I A056619 #30 Aug 13 2021 19:15:59
%S A056619 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 A056619 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 A056619 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 A056619 Smallest prime with primitive root n, or 0 if no such prime exists.
%C A056619 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 A056619 Robert Israel, <a href="/A056619/b056619.txt">Table of n, a(n) for n = 1..10000</a>
%F A056619 a(n) = 0 only for perfect squares, A000290.
%F A056619 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 A056619 f:= proc(n) local p;
%p A056619    if n::odd then return 2
%p A056619    elif issqr(n) then return 0
%p A056619    fi;
%p A056619    p:= 3;
%p A056619    do
%p A056619       if numtheory:-order(n,p) = p-1 then return p fi;
%p A056619       p:= nextprime(p);
%p A056619    od
%p A056619 end proc:
%p A056619 map(f, [$1..100]); # _Robert Israel_, Feb 21 2017
%t A056619 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 A056619 Array[a, 100] (* _Jean-François Alcover_, Apr 10 2019, after _Robert Israel_ *)
%o A056619 (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 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 A056619 Here the primitive root may be larger than the prime, whereas in A023049 it may not be.
%Y A056619 Cf. A001122, A001913, A019334-A019421.
%K A056619 nonn
%O A056619 1,1
%A A056619 _Robert G. Wilson v_, Aug 07 2000
%E A056619 Corrected and extended by _Jud McCranie_, Mar 21 2002
%E A056619 Corrected by _Robert Israel_, Feb 21 2017