BBC Russian

A328496

Triangular array read by rows: for 1 <= k <= n, T(n,k) is the number of x in [1,k] such that gcd(n,x) > 1 and gcd(k,x) > 1.

0, 0, 1, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 0, 1, 0, 1, 1, 2, 0, 4, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 4, 0, 0, 1, 0, 0, 2, 0, 1, 3, 0, 1, 0, 2, 1, 3, 0, 4, 1, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 0, 4, 0, 4, 3, 5, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,10

COMMENTS

T(n,k)=0 if n is prime and k < n, or if k is prime and n is not a multiple of k.

T(n,k) <= min(n-phi(n), k-phi(k)).

LINKS

Robert Israel, Table of n, a(n) for n = 1..10011 (rows 1 to 141, flattened)

EXAMPLE

T(6,4) = 2 because there are two numbers in [1,2,3,4] that are not coprime to either 6 or 4, namely 2 and 4.

First 8 rows:

0, 1;

0, 0, 1;

0, 1, 0, 2;

0, 0, 0, 0, 1;

0, 1, 1, 2, 0, 4;

0, 0, 0, 0, 0, 0, 1;

0, 1, 0, 2, 0, 3, 0, 4;

MAPLE

f:= proc(a, b) local i;

nops(select(t -> igcd(t, a)>1 and igcd(t, b)>1, [seq(i, i=1..min(a, b))]))

end proc:

seq(seq(f(a, b), b=1..a), a=1..15);

CROSSREFS

Cf. A051953 (T(n,n)).

Sequence in context: A188171 A363807 A330733 * A035202 A227835 A281154

Adjacent sequences: A328493 A328494 A328495 * A328497 A328498 A328499

KEYWORD

nonn,tabl

AUTHOR

Robert Israel, Oct 16 2019

STATUS

approved