A377938 - OEIS

%I #12 Nov 11 2024 22:26:08

%S 2,3,4,-1,6,11,10,11,-1,17,13,17,19,17,19,-1,22,29,22,23,23,25,25,31,

%T -1,29,29,41,34,41,34,37,38,41,37,-1,46,47,47,47,47,59,46,47,47,67,49,

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

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

%C a(n) <= A023049(n).

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

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

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

%p N:= 1000: # to allow values <= N

%p P:= select(isprime, {seq(i,i=3..N,2)}):

%p 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):

%p Cands:= sort(convert({4} union Cands, list)):

%p Phis:= map(numtheory:-phi, Cands):

%p f:= proc(n)

%p local k0,k;

%p       if issqr(n) then return -1 fi;

%p       k0:= ListTools:-BinaryPlace(Cands,n)+1;

%p       for k from k0 do

%p         if igcd(Cands[k],n) = 1 and numtheory:-order(n,Cands[k]) = Phis[k] then return Cands[k] fi

%p       od

%p end proc:

%p f(1):= 2:

%p map(f, [$1..200]);

%Y Cf. A023049, A377939. A377940.

%K sign

%O 1,1

%A _Robert Israel_, Nov 11 2024