A300064 Numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

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

Author

Max Alekseyev, Feb 23 2018

Keywords

• nonn

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

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• 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.

Crossrefs

Complement of A300065.

Set union of A300079 and A000040.

Set union of A300080 and A000961 \ {8}.

Cf. A000010, A002322, A010554, A111725.

Programs

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

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