OFFSET
1,3
COMMENTS
Let U(k) denote the multiplicative group mod k. a(n) = largest generator for U(A033948(n)). - N. J. A. Sloane, Mar 10 2019
LINKS
Robert Israel, Table of n, a(n) for n = 1..10000
EXAMPLE
For n=2, U(n) is generated by 1.
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.
MAPLE
f:= proc(b) local x, t;
t:= numtheory:-phi(b);
for x from b-1 by -1 do if igcd(x, b) = 1 and numtheory:-order(x, b)=t then return x fi od
end proc:
f(1):= 0:
cands:= select(t -> t=1 or numtheory:-primroot(t) <> FAIL, [$1..1000]):
map(f, cands); # Robert Israel, Mar 10 2019
MATHEMATICA
Join[{0}, Last /@ DeleteCases[PrimitiveRootList[Range[1000]], {}]] (* Jean-François Alcover, Jun 18 2020 *)
PROG
(Python)
def gcd(x, y):
# Euclid's Algorithm
while(y):
x, y = y, x % y
return x
roots = []
for n in range(2, 140):
# find U(n)
un = [i for i in range(n, 0, -1) if (gcd(i, n) is 1)]
# for each element in U(n), check if it's a generator
order = len(un)
is_cyclic = False
for cand in un:
is_gen = True
run = 1
# If it cand^x = 1 for some x < order, it's not a generator
for _ in range(order-1):
run = (run * cand) % n
if run == 1:
is_gen = False
break
if is_gen:
roots.append(cand)
is_cyclic = True
break
print("roots:", roots)
CROSSREFS
KEYWORD
nonn
AUTHOR
Charles Paul, Feb 01 2019
EXTENSIONS
Edited by N. J. A. Sloane, Mar 10 2019.
STATUS
approved