cp's OEIS Frontend

A074919 Number of integers in {1, 2, ..., phi(n)} that are coprime to n.

%I A074919 #11 Sep 17 2022 05:26:20
%S A074919 1,1,2,1,4,1,6,2,4,2,10,1,12,3,5,4,16,2,18,3,7,5,22,3,16,6,12,5,28,2,
%T A074919 30,8,13,8,17,4,36,9,15,6,40,3,42,9,13,11,46,5,36,8,21,11,52,6,29,10,
%U A074919 23,14,58,4,60,15,20,16,36,6,66,15,29,8,70,8,72,18,21,17,47,7,78,13,36
%N A074919 Number of integers in {1, 2, ..., phi(n)} that are coprime to n.
%C A074919 Compare the definition of a(n) to phi(n) = number of integers in {1, 2, ..., n} that are coprime to n.
%F A074919 a(n) = Sum_{d|n} mu(d)*floor(phi(n)/d). - _Ridouane Oudra_, Sep 16 2022
%e A074919 There are four numbers in {1, 2, ..., phi(8) = 4} that are coprime to 8, i.e. 1, 3. Hence a(8) = 2.
%p A074919 A074919 := proc(n)
%p A074919     local a,k ;
%p A074919     a := 0 ;
%p A074919     for k from 1 to numtheory[phi](n) do
%p A074919         if igcd(k,n) = 1 then
%p A074919             a := a+1 ;
%p A074919         end if;
%p A074919     end do:
%p A074919     a ;
%p A074919 end proc:
%p A074919 seq(A074919(n),n=1..30) ; # _R. J. Mathar_, Feb 21 2017
%t A074919 h[n_] := Module[{l}, l = {}; For[i = 1, i <= EulerPhi[n], i++, If[GCD[i, n] == 1, l = Append[l, i]]]; l]; Table[Length[h[i]], {i, 1, 100}]
%o A074919 (PARI) a(n)=sum(k=1,eulerphi(n),1==gcd(k,n)); \\ _Joerg Arndt_, Feb 21 2017
%Y A074919 Cf. A000010.
%K A074919 nonn
%O A074919 1,3
%A A074919 _Joseph L. Pe_, Oct 04 2002