A078401 Triangle read by rows: T(n,k) = number of numbers <= k that are coprime to n, 1<=k<=n.

1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 3, 4, 4, 1, 1, 1, 1, 2, 2, 1, 2, 3, 4, 5, 6, 6, 1, 1, 2, 2, 3, 3, 4, 4, 1, 2, 2, 3, 4, 4, 5, 6, 6, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5

Offset

1,5

Comments

T(n,1) = 1; T(n,n) = phi(n), where phi is Euler's totient function (A000010); for p prime: T(p,i) = i for 1<=i<p and T(p,p) = p-1.

Links

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

Eric Weisstein's World of Mathematics, Sieve of Eratosthenes.

Eric Weisstein's World of Mathematics, Legendre's Formula.

Formula

T(n,k) = Sum{mu(d)*floor(k/d): n mod d = 0}, where mu is the Moebius Function (A008683).

Example

1,
1, 1,
1, 2, 2,
1, 1, 2, 2,
1, 2, 3, 4, 4,
1, 1, 1, 1, 2, 2,
1, 2, 3, 4, 5, 6, 6,
1, 1, 2, 2, 3, 3, 4, 4,
1, 2, 2, 3, 4, 4, 5, 6, 6,
1, 1, 2, 2, 2, 2, 3, 3, 4, 4,

Maple

A078401 := proc(n, k)
    a := 0 ;
    for j from 1 to k do
        if igcd(j, n) = 1 then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Jul 21 2016

Mathematica

T[n_, k_] := Count[Range[k], d_ /; CoprimeQ[n, d]];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 13 2018 *)

Crossrefs

Sequence in context: A298231 A320473 A194884 * A271381 A086247 A116452

Adjacent sequences: A078398 A078399 A078400 * A078402 A078403 A078404

Keyword

nonn,tabl,easy

Author

Reinhard Zumkeller, Dec 25 2002

Extensions

Thanks to Duc Ngo Minh (ducnm0(AT)gmail.com) who noticed an error in the formula; corrected by Reinhard Zumkeller, Mar 01 2009

Status

approved