A377938 a(n) is the least k > n such that n is a primitive root modulo k, or -1 if there is no such k.

2, 3, 4, -1, 6, 11, 10, 11, -1, 17, 13, 17, 19, 17, 19, -1, 22, 29, 22, 23, 23, 25, 25, 31, -1, 29, 29, 41, 34, 41, 34, 37, 38, 41, 37, -1, 46, 47, 47, 47, 47, 59, 46, 47, 47, 67, 49, 53, -1, 53, 53, 59, 62, 59, 58, 59, 67, 73, 61, 73, 67, 71, 67, -1, 71, 79, 71, 71, 71, 79, 82, 83, 83, 79, 79

Offset: 1

Author

Robert Israel, Nov 11 2024

Keywords

• sign

Comments

a(n) <= A023049(n).

a(n) = 0 iff n is a square > 1.

Examples

			a(6) = 11 because 6 is a primitive root mod 11 and no number from 7 to 10 has 6 as a primitive root.
		

Links

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

Crossrefs

Cf. A023049, A377939. A377940.

Programs

Maple

N:= 1000: # to allow values <= N
P:= select(isprime, {seq(i,i=3..N,2)}):
Cands:= map(proc(t) local i; (seq(t^i,i=1..ilog[t](N)), seq(2*t^i,i=1..ilog[t](N/2))) end proc,P):
Cands:= sort(convert({4} union Cands, list)):
Phis:= map(numtheory:-phi, Cands):
f:= proc(n)
local k0,k;
      if issqr(n) then return -1 fi;
      k0:= ListTools:-BinaryPlace(Cands,n)+1;
      for k from k0 do
        if igcd(Cands[k],n) = 1 and numtheory:-order(n,Cands[k]) = Phis[k] then return Cands[k] fi
      od
end proc:
f(1):= 2:
map(f, [$1..200]);