cp's OEIS Frontend

A306253 Largest primitive root mod A033948(n).

%I A306253 #23 May 17 2025 17:06:05
%S A306253 0,1,2,3,3,5,5,5,7,8,11,5,14,11,15,19,21,23,19,23,27,24,31,35,33,35,
%T A306253 34,43,45,47,47,51,47,55,56,59,55,63,69,68,69,77,77,75,80,77,86,91,92,
%U A306253 89,99,101,103,104,103,110,115,117,115,123,118,128,117,134,135
%N A306253 Largest primitive root mod A033948(n).
%C A306253 Let U(k) denote the multiplicative group mod k. a(n) = largest generator for U(A033948(n)). - _N. J. A. Sloane_, Mar 10 2019
%H A306253 Robert Israel, <a href="/A306253/b306253.txt">Table of n, a(n) for n = 1..10000</a>
%e A306253 For n=2, U(n) is generated by 1.
%e A306253 For n=14, A033948(14) = 18, and, U(n) is generated by both 5 and 11; here we select the largest generator, 11, so a(14) = 11.
%p A306253 f:= proc(b) local x, t;
%p A306253   t:= numtheory:-phi(b);
%p A306253   for x from b-1 by -1 do if igcd(x,b) = 1 and numtheory:-order(x,b)=t then return x fi od
%p A306253 end proc:
%p A306253 f(1):= 0:
%p A306253 cands:= select(t -> t=1 or numtheory:-primroot(t) <> FAIL, [$1..1000]):
%p A306253 map(f, cands); # _Robert Israel_, Mar 10 2019
%t A306253 Join[{0}, Last /@ DeleteCases[PrimitiveRootList[Range[1000]], {}]] (* _Jean-François Alcover_, Jun 18 2020 *)
%o A306253 (Python)
%o A306253 def gcd(x, y):
%o A306253     # Euclid's Algorithm
%o A306253     while(y):
%o A306253         x, y = y, x % y
%o A306253     return x
%o A306253 roots = [0]
%o A306253 for n in range(2, 140):
%o A306253     # find U(n)
%o A306253     un = [i for i in range(n, 0, -1) if (gcd(i, n) == 1)]
%o A306253     # for each element in U(n), check if it's a generator
%o A306253     order = len(un)
%o A306253     is_cyclic = False
%o A306253     for cand in un:
%o A306253         is_gen = True
%o A306253         run = 1
%o A306253         # If it cand^x = 1 for some x < order, it's not a generator
%o A306253         for _ in range(order-1):
%o A306253             run = (run * cand) % n
%o A306253             if run == 1:
%o A306253                 is_gen = False
%o A306253                 break
%o A306253         if is_gen:
%o A306253             roots.append(cand)
%o A306253             is_cyclic = True
%o A306253             break
%o A306253 print("roots:", roots)
%Y A306253 See A306252 for smallest roots and A033948 for the sequence of numbers that have a primitive root.
%K A306253 nonn
%O A306253 1,3
%A A306253 _Charles Paul_, Feb 01 2019
%E A306253 Edited by _N. J. A. Sloane_, Mar 10 2019.