%I #16 Jun 01 2024 09:44:17
%S 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,
%T 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,
%U 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
%N Triangle read by rows: T(n,k) = number of numbers <= k that are coprime to n, 1 <= k <= n.
%C 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.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SieveofEratosthenes.html">Sieve of Eratosthenes</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LegendresFormula.html">Legendre's Formula</a>.
%F T(n,k) = Sum_{mu(d)*floor(k/d): n mod d = 0}, where mu is the Moebius Function (A008683).
%e Triangle begins
%e 1;
%e 1, 1;
%e 1, 2, 2;
%e 1, 1, 2, 2;
%e 1, 2, 3, 4, 4;
%e 1, 1, 1, 1, 2, 2;
%e 1, 2, 3, 4, 5, 6, 6;
%e 1, 1, 2, 2, 3, 3, 4, 4;
%e 1, 2, 2, 3, 4, 4, 5, 6, 6;
%e 1, 1, 2, 2, 2, 2, 3, 3, 4, 4;
%e ...
%p A078401 := proc(n,k)
%p a := 0 ;
%p for j from 1 to k do
%p if igcd(j,n) = 1 then
%p a := a+1 ;
%p end if;
%p end do:
%p a ;
%p end proc: # _R. J. Mathar_, Jul 21 2016
%t T[n_, k_] := Count[Range[k], d_ /; CoprimeQ[n, d]];
%t Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Feb 13 2018 *)
%K nonn,tabl,easy
%O 1,5
%A _Reinhard Zumkeller_, Dec 25 2002
%E Thanks to Duc Ngo Minh (ducnm0(AT)gmail.com), who noticed an error in the formula; corrected by _Reinhard Zumkeller_, Mar 01 2009