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

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, 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, 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

Offset: 1

Author

Joseph L. Pe, Oct 04 2002

Keywords

• nonn

Comments

Compare the definition of a(n) to phi(n) = number of integers in {1, 2, ..., n} that are coprime to n.

Examples

			There are four numbers in {1, 2, ..., phi(8) = 4} that are coprime to 8, i.e. 1, 3. Hence a(8) = 2.
		

Crossrefs

Cf. A000010.

Programs

Maple

A074919 := proc(n)
    local a,k ;
    a := 0 ;
    for k from 1 to numtheory[phi](n) do
        if igcd(k,n) = 1 then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:
seq(A074919(n),n=1..30) ; # R. J. Mathar, Feb 21 2017

Mathematica

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}]

PARI

a(n)=sum(k=1,eulerphi(n),1==gcd(k,n)); \\ Joerg Arndt, Feb 21 2017

Formula

a(n) = Sum_{d|n} mu(d)*floor(phi(n)/d). - Ridouane Oudra, Sep 16 2022