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