A066678 Totients of the least numbers for which the totient is divisible by n.

1, 2, 6, 4, 10, 6, 28, 8, 18, 10, 22, 12, 52, 28, 30, 16, 102, 18, 190, 20, 42, 22, 46, 24, 100, 52, 54, 28, 58, 30, 310, 32, 66, 102, 70, 36, 148, 190, 78, 40, 82, 42, 172, 44, 180, 46, 282, 48, 196, 100, 102, 52, 106, 54, 110, 56, 228, 58, 708, 60, 366, 310, 126, 64

Offset: 1

Author

Labos Elemer, Dec 22 2001

Keywords

• nonn

Comments

From Alonso del Arte, Feb 03 2017: (Start)

One of the less obvious consequences of Dirichlet's theorem on primes in arithmetic progression is that this sequence is well-defined for all positive integers.

Suppose n is a nontotient (see A007617). Obviously a(n) != n. Dirichlet's theorem assures us that, if nothing else, there are infinitely many primes of the form nk + 1 for k positive (and in this case, k > 1). Then phi(nk + 1) = nk, suggesting a(n) = nk corresponding to the smallest k.

Of course not all a(n) are 1 less than a prime, such as 8, 20, 24, 54, etc. (End)

Examples

			a(23) = 46 because there is no solution to phi(x) = 23 but there are solutions to phi(x) = 46, like x = 47.
a(24) = 24 because there are solutions to phi(x) = 24, such as x = 35.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5000 from Vincenzo Librandi)

Crossrefs

Cf. A000010, A066674, A066675, A066676, A066677, A067005, A061026.

Programs

Mathematica

EulerPhi[mulTotientList = ConstantArray[1, 70]; k = 1; While[Length[vac = Rest[Flatten[Position[mulTotientList, 1]]]] > 0, k++; mulTotientList[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; mulTotientList] (* Vincenzo Librandi Feb 04 2017 *)
a[n_] := For[k=1, True, k++, If[Divisible[t = EulerPhi[k], n], Return[t]]];
Array[a, 64] (* Jean-François Alcover, Jul 30 2018 *)

PARI

list(len) = {my(v = vector(len), c = 0, k = 1, e); while(c < len, e = eulerphi(k); fordiv(e, d, if(d <= len && v[d] == 0, v[d] = e; c++)); k++); v;} \\ Amiram Eldar, Mar 07 2025

Sage

def A066678(n):
    s = 1
    while euler_phi(s) % n: s += 1
    return euler_phi(s)
print([A066678(n) for n in (1..64)]) # Peter Luschny, Feb 05 2017

Formula

a(n) = A000010(A061026(n)).