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
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
KEYWORD
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