cp's OEIS Frontend

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

%I A066678 #33 Mar 07 2025 02:56:09
%S A066678 1,2,6,4,10,6,28,8,18,10,22,12,52,28,30,16,102,18,190,20,42,22,46,24,
%T A066678 100,52,54,28,58,30,310,32,66,102,70,36,148,190,78,40,82,42,172,44,
%U A066678 180,46,282,48,196,100,102,52,106,54,110,56,228,58,708,60,366,310,126,64
%N A066678 Totients of the least numbers for which the totient is divisible by n.
%C A066678 From _Alonso del Arte_, Feb 03 2017: (Start)
%C A066678 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.
%C A066678 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.
%C A066678 Of course not all a(n) are 1 less than a prime, such as 8, 20, 24, 54, etc. (End)
%H A066678 Amiram Eldar, <a href="/A066678/b066678.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..5000 from Vincenzo Librandi)
%F A066678 a(n) = A000010(A061026(n)).
%e A066678 a(23) = 46 because there is no solution to phi(x) = 23 but there are solutions to phi(x) = 46, like x = 47.
%e A066678 a(24) = 24 because there are solutions to phi(x) = 24, such as x = 35.
%t A066678 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 *)
%t A066678 a[n_] := For[k=1, True, k++, If[Divisible[t = EulerPhi[k], n], Return[t]]];
%t A066678 Array[a, 64] (* _Jean-François Alcover_, Jul 30 2018 *)
%o A066678 (Sage)
%o A066678 def A066678(n):
%o A066678     s = 1
%o A066678     while euler_phi(s) % n: s += 1
%o A066678     return euler_phi(s)
%o A066678 print([A066678(n) for n in (1..64)]) # _Peter Luschny_, Feb 05 2017
%o A066678 (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
%Y A066678 Cf. A000010, A066674, A066675, A066676, A066677, A067005, A061026.
%K A066678 nonn
%O A066678 1,2
%A A066678 _Labos Elemer_, Dec 22 2001