%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