login
Least primitive root mod A033948(n).
4

%I #27 May 09 2021 06:23:17

%S 0,1,2,3,2,5,3,2,3,2,2,3,3,5,2,7,5,2,7,2,2,3,3,2,3,6,3,5,5,3,3,2,5,3,

%T 2,2,3,2,7,5,5,3,2,7,2,3,3,5,5,3,2,5,3,2,6,3,11,2,7,2,3,2,7,3,2,7,5,2,

%U 6,5,3,5,2,5,5,2,2,3,2,2,19,5,5,2,3,3,5

%N Least primitive root mod A033948(n).

%C Let U(k) denote the multiplicative group mod k. a(n) = smallest generator for U(A033948(n)). - _N. J. A. Sloane_, Mar 10 2019

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

%e For n=2, A033948(2) = 2, U(2) is generated by 1.

%e For n=14, A033948(14) = 18, and U(18) is generated by both 5 and 11; here we select the smallest generator, 5, so a(14) = 5.

%p 0,op(subs(FAIL=NULL, map(numtheory:-primroot,[$2..1000]))); # _Robert Israel_, Mar 10 2019

%t Array[Take[PrimitiveRootList@ #, UpTo[1]] &, 210] // Flatten (* _Michael De Vlieger_, Feb 02 2019 *)

%o (Python)

%o from math import gcd

%o roots = [0]

%o for n in range(2,140):

%o # find U(n)

%o un = [i for i in range(1,n) if gcd(i,n) == 1]

%o # for each element in U(n), check if it's a generator

%o order = len(un)

%o is_cyclic = False

%o for cand in un:

%o is_gen = True

%o run = 1

%o # If it cand^x = 1 for some x < order, it's not a generator

%o for _ in range(order-1):

%o run = (run * cand) % n

%o if run == 1:

%o is_gen = False

%o break

%o if is_gen:

%o roots.append(cand)

%o is_cyclic = True

%o break

%o print(roots)

%Y Cf. A033948 (numbers that have a primitive root), A306253, A081888 (positions of records), A081889 (record values). First column of A046147.

%K nonn

%O 1,3

%A _Charles Paul_, Feb 01 2019

%E More terms from _Michael De Vlieger_, Feb 02 2019

%E Edited by _N. J. A. Sloane_, Mar 10 2019

%E Edited by _Robert Israel_, Mar 10 2019