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,13

Links

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

Example

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,
...

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 *)

Crossrefs

Row sums give A049817.

Sequence in context: A114448 A068933 A015472 * A328958 A143542 A072612

Adjacent sequences: A049813 A049814 A049815 * A049817 A049818 A049819

Keyword

nonn,tabl

Author

Clark Kimberling

Status

approved