login
A300064
Numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.
5
1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 29, 30, 31, 32, 34, 35, 37, 38, 39, 40, 41, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 58, 59, 60, 61, 62, 64, 67, 68, 70, 71, 73, 74, 75, 78, 79, 81, 82, 83, 85, 86, 87, 89, 90, 94, 95, 96, 97, 98, 100, 101, 102, 103, 104, 105, 106, 107, 109, 110
OFFSET
1,2
COMMENTS
Numbers k such that A111725(k) = A010554(k).
Contains subsequences of the primes (A000040) and the prime powers (A000961) except 2^3 = 8.
The ratio a(n)/n tends to infinity as n grows (Müller and Schlage-Puchta, 2004).
Decompose (Z/kZ)* as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then k is a term if and only if m <= 1, or v(k_{m-1},p) < v(k_m,p) holds for all primes p dividing k_m = psi(k), where v(s,p) is the p-adic valuation of s. Otherwise, there are more than phi(phi(k)) residues modulo k of the maximum order. See my Oct 12 2021 formula for A111725 for a proof. - Jianing Song, Oct 20 2021
LINKS
Peter J. Cameron and D. A. Preece, Primitive lambda-roots, 2014.
T. W. Müller and J.-C. Schlage-Puchta, On the number of primitive lambda-roots, Acta Arithmetica, Vol. 115 (2004), pp. 217-223.
MATHEMATICA
q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] == EulerPhi[EulerPhi[n]]; Select[Range[100], q] (* Amiram Eldar, Oct 12 2021 *)
PROG
(PARI) isA300064(n) = my(v=znstar(n)[2], l=#v); if(l<2, return(1), my(U=v[1], L=v[2], d=factor(U), w=omega(U)); for(i=1, w, if(valuation(L, d[i, 1]) == d[i, 2], return(0))); return(1)) \\ Jianing Song, Oct 20 2021
CROSSREFS
Complement of A300065.
Set union of A300079 and A000040.
Set union of A300080 and A000961 \ {8}.
Sequence in context: A191852 A136416 A072497 * A039217 A239289 A131511
KEYWORD
nonn
AUTHOR
Max Alekseyev, Feb 23 2018
STATUS
approved