A377939 -id:A377939 - cp's OEIS frontend

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

David W. Wilson

nonn

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

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

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

Cf. A377938, A377939.

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

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 *)

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

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

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.

Original entry on oeis.org

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

Robert Israel, Nov 11 2024

sign

a(n) <= A023049(n).

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

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

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

Cf. A023049, A377939. A377940.

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]);

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula