cp's OEIS Frontend

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

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