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

Comments

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

Links

Table of n, a(n) for n=1..81.

Formula

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

Example

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

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

Prog

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

Crossrefs

Cf. A000010.

Sequence in context: A074643 A060794 A300716 * A362232 A138009 A131755

Adjacent sequences: A074916 A074917 A074918 * A074920 A074921 A074922

Keyword

nonn

Author

Joseph L. Pe, Oct 04 2002

Status

approved