A049816 Triangular array T read by rows: T(n,k) = number of nonzero remainders when Euclidean algorithm acts on n and k, for k=1..n, n>=1.

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

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• tabl

Examples

			Triangle begins:
0,
0, 0,
0, 1, 0,
0, 0, 1, 0,
0, 1, 2, 1, 0,
0, 0, 0, 1, 1, 0,
0, 1, 1, 2, 2, 1, 0,
0, 0, 2, 0, 3, 1, 1, 0,
0, 1, 0, 1, 2, 1, 2, 1, 0,
0, 0, 1, 1, 0, 2, 2, 1, 1, 0,
0, 1, 2, 2, 1, 2, 3, 3, 2, 1, 0,
0, 0, 0, 0, 2, 0, 3, 1, 1, 1, 1, 0,
0, 1, 1, 1, 3, 1, 2, 4, 2, 2, 2, 1, 0,
...
		

Links

• Alois P. Heinz, Rows n = 1..200, flattened

Crossrefs

Row sums give A049817.

Programs

Maple

T:= proc(x, y) option remember;
      `if`(y=0, -1, 1+T(y, irem(x, y)))
    end:
seq(seq(T(n, k), k=1..n), n=1..15);  # Alois P. Heinz, Nov 29 2023

Mathematica

R[n_, k_] := R[n, k] = With[{r = Mod[n, k]}, If[r == 0, 1, R[k, r] + 1]];
T[n_, k_] := R[n, k] - 1;
Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 12 2019, after Robert Israel in A107435 *)