A023049 Smallest prime > n having primitive root n, or 0 if no such prime exists.

2, 3, 5, 0, 7, 11, 11, 11, 0, 17, 13, 17, 19, 17, 19, 0, 23, 29, 23, 23, 23, 31, 47, 31, 0, 29, 29, 41, 41, 41, 47, 37, 43, 41, 37, 0, 59, 47, 47, 47, 47, 59, 47, 47, 47, 67, 59, 53, 0, 53, 53, 59, 71, 59, 59, 59, 67, 73, 61, 73, 67, 71, 67, 0, 71, 79, 71, 71, 71, 79, 83, 83, 83, 79

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Comments

Indices of record values of a(n)-n are (1, 2, 3, 6, 10, 18, 23, 78, 102, 105, 488, 652, 925, ...). Record values of a(n)/n are 3/2, 5/3, 11/6, 47/23, ... (Is there another n with a(n) > 2n ?) - M. F. Hasler, Feb 21 2017

Links

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

Crossrefs

See also A056619, where the primitive root may be larger than the prime, whereas in A023049 it may not be.

Cf. A377938, A377939.

Programs

Maple

f:= proc(n) local p;
  if issqr(n) then return 0 fi;
  p:= nextprime(n);
  do
    if numtheory:-order(n,p) = p-1 then return p fi;
    p:= nextprime(p);
  od
end proc:
f(1):= 2:
map(f, [$1..100]); # Robert Israel, Feb 21 2017

Mathematica

a[n_] := For[p = 2, p <= 2 n + 1, p = NextPrime[p], If[MemberQ[ PrimitiveRootList[p], n], Return[p]]] /. Null -> 0; Array[a, 100] (* Jean-François Alcover, Mar 05 2019 *)

PARI

A023049(n)={issquare(n)||forprime(p=n+1,,znorder(Mod(n,p))==p-1&&return(p));(n==1)*2} \\ M. F. Hasler, Feb 21 2017

Formula

a(n) = 0 iff n is a square > 1. - M. F. Hasler, Feb 21 2017