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

Triangle begins
  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 * A372673 A271381 A086247

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