A076221 Triangle read by rows: A(n,k) is the number of x, x<=n, which are coprime to and not equal to k.

0, 1, 1, 2, 2, 2, 3, 2, 3, 2, 4, 3, 4, 3, 4, 5, 3, 4, 3, 5, 2, 6, 4, 5, 4, 6, 3, 6, 7, 4, 6, 4, 7, 3, 7, 4, 8, 5, 6, 5, 8, 3, 8, 5, 6, 9, 5, 7, 5, 8, 3, 9, 5, 7, 4, 10, 6, 8, 6, 9, 4, 10, 6, 8, 5, 10, 11, 6, 8, 6, 10, 4, 11, 6, 8, 5, 11, 4, 12, 7, 9, 7, 11, 5, 12, 7, 9, 6, 12, 5, 12

Offset: 1

Author

Olivier Gérard

Keywords

• nonn
• tabl

Comments

Last entry of each row is Euler totient function phi(n).

{{0}, {1, 1}, {2, 2, 2}, {3, 2, 3, 2}, {4, 3, 4, 3, 4}, {5, 3, 4, 3, 5, 2}}

Examples

			a(20)=A(6,5) is 5 because (1,5), (2,5), (3,5), (4,5) and (5,6) are the five pairs of relatively primes integers <= 6.
Triangle begins:
  0,
  1, 1,
  2, 2, 2,
  3, 2, 3, 2,
  4, 3, 4, 3, 4,
  5, 3, 4, 3, 5, 2,
  ...
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10011

Programs

Maple

f:= proc(n,k) if k=1 then n-1 else  nops(select(t -> igcd(k,t)=1, [$1..n])) fi end proc:
seq(seq(f(n,k),k=1..n),n=1..30); # Robert Israel, Aug 29 2016

Mathematica

A[n_, k_] := Count[Range[n], x_ /; CoprimeQ[x, k] && x != k];
Table[A[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 05 2019 *)

Extensions

Definition and example corrected by Robert Israel, Aug 29 2016