A377402 Least k such that the ratio of the number of residues mod k coprime to k and the number of primitive roots mod k is greater than or equal to n for k such that at least one primitive root mod k exists. Equivalently, k such that floor(phi(k)/phi(phi(k)) is a record value for those k belonging to A033948.

1, 3, 7, 211, 43891, 300690391

Offset: 1

Author

Miles Englezou, Oct 26 2024

Keywords

• nonn
• more

Comments

These are the numbers k with the least proportion of primitive roots mod k to residues mod k coprime to k, of all m < k.

Let U(k) be the group of units of the ring Z/kZ, and Gen(k) the set of distinct single element generators of U(k). Then a(n) is equivalently those k for which floor(|U(k)|/|Gen(k)|) is a record value for those k with cyclic U(k).

Some data:

---------------------------------------------------------------------------------

n a(n) log(a(n)) phi(a(n)) max prime(r)#|phi(a(n)) r

---------------------------------------------------------------------------------

1 1 0 1 0 0

2 3 1.10... 2 2 1

3 7 1.96... 2*3 6 2

4 211 5.35... 2*3*5*7 210 4

5 43891 10.69... 2*3*5*7*11*19 2310 5

6 300690391 19.52... 2*3*5*7*11*13*17*19*31 9699690 8

---------------------------------------------------------------------------------

For n > 1, is a(n) necessarily prime? Furthermore, is a(n) necessarily a prime such that phi(a(n)) is squarefree? Lastly, is every phi(a(n)) divisible by a maximal primorial prime(r)# of length r <= omega(phi(a(n))), such that if a maximal prime(s)# divides phi(a(m)) and n < m, then r < s?

Based on the behavior of log(a(n)), we may expect a(7) to be found in the vicinity of floor(exp(40)) = 235385266837019985.

Examples

			There are 2 residues mod 3 coprime to 3, and only 1 is a primitive root. 3 is the least k for which the floor of the ratio is 2, and so a(2) = 3.
There are 210 residues mod 211 coprime to 211, and 48 are primitive roots. Floor(210/48) = 4, and 211 is the least k for which the floor of the ratio is 4, and so a(4) = 211.
		

Crossrefs

Cf. A000010, A010554, A033948, A046144.

Programs

PARI

S=[1]; for(n=1,100000, if(#znstar(n).cyc>1,next); f=eulerphi; if(floor(f(n)/f(f(n)))>floor(f(S[length(S)])/f(f(S[length(S)]))), S=concat(S,n))); print(S)

Formula

Numbers k for which floor(A000010(A033948(k))/A046144(A033948(k)) is a record value.