|
%I #11 Sep 17 2022 05:26:20
%S 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 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 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 Number of integers in {1, 2, ..., phi(n)} that are coprime to n.
%C Compare the definition of a(n) to phi(n) = number of integers in {1, 2, ..., n} that are coprime to n.
%F a(n) = Sum_{d|n} mu(d)*floor(phi(n)/d). - _Ridouane Oudra_, Sep 16 2022
%e 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 := proc(n)
%p local a,k ;
%p a := 0 ;
%p for k from 1 to numtheory[phi](n) do
%p if igcd(k,n) = 1 then
%p a := a+1 ;
%p end if;
%p end do:
%p a ;
%p end proc:
%p seq(A074919(n),n=1..30) ; # _R. J. Mathar_, Feb 21 2017
%t 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 (PARI) a(n)=sum(k=1,eulerphi(n),1==gcd(k,n)); \\ _Joerg Arndt_, Feb 21 2017
%Y Cf. A000010.
%K nonn
%O 1,3
%A _Joseph L. Pe_, Oct 04 2002
|
