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

Offset: 1

Author

Reinhard Zumkeller, Dec 25 2002

Keywords

• nonn
• tabl
• easy

Examples

			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;
  ...
		

Links

• Eric Weisstein's World of Mathematics, Legendre's Formula.
• Eric Weisstein's World of Mathematics, Sieve of Eratosthenes.

Crossrefs

Cf. A000010, A008683, A092790.

Programs

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 *)
row[n_] := Accumulate[Table[Boole[CoprimeQ[n, k]], {k, n}]]; Array[row, 14] // Flatten (* Amiram Eldar, May 12 2025 *)

PARI

row(n) = {my(v = vector(n, k, gcd(n,k)==1)); for(k = 2, n, v[k] += v[k-1]); v;} \\ Amiram Eldar, May 12 2025

Formula

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.

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

Sum_{k=1..n} T(n,k) = (n+2)*phi(n)/2 = A092790(n+1) for n >= 2. - Amiram Eldar, May 12 2025

Extensions

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