A306253 Largest primitive root mod A033948(n).

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, 34, 43, 45, 47, 47, 51, 47, 55, 56, 59, 55, 63, 69, 68, 69, 77, 77, 75, 80, 77, 86, 91, 92, 89, 99, 101, 103, 104, 103, 110, 115, 117, 115, 123, 118, 128, 117, 134, 135

Offset: 1

Author

Charles Paul, Feb 01 2019

Keywords

• nonn

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

Examples

			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.
		

Links

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

Crossrefs

See A306252 for smallest roots and A033948 for the sequence of numbers that have a primitive root.

Programs

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

Python

def gcd(x, y):
    # Euclid's Algorithm
    while(y):
        x, y = y, x % y
    return x
roots = [0]
for n in range(2, 140):
    # find U(n)
    un = [i for i in range(n, 0, -1) if (gcd(i, n) == 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)

Extensions

Edited by N. J. A. Sloane, Mar 10 2019.