A049840 Triangular array T read by rows: T(n,k) = sum of numbers c in the form c = bq + r when Euclidean algorithm acts on n, k, for 1 <= k <= n, n >= 1.

1, 2, 2, 3, 5, 3, 4, 4, 7, 4, 5, 7, 10, 9, 5, 6, 6, 6, 10, 11, 6, 7, 9, 10, 14, 14, 13, 7, 8, 8, 13, 8, 18, 14, 15, 8, 9, 11, 9, 13, 18, 15, 18, 17, 9, 10, 10, 13, 14, 10, 20, 20, 18, 19, 10, 11, 13, 16, 18, 16, 22, 25, 24, 22, 21, 11, 12, 12, 12, 12, 19, 12, 26, 20, 21, 22, 23, 12

Offset

1,2

Links

G. C. Greubel, Rows n=1..100 of triangle, flattened

Formula

T(n,0) = 0, T(n,k) = n + T(k, n mod k). - Charlie Neder, Mar 10 2019

Example

Triangle begins with:
  1;
  2,  2;
  3,  5,  3;
  4,  4,  7,  4;
  5,  7, 10,  9,  5;
  6,  6,  6, 10, 11,  6; ...
Example: 5=1*3+2; 3=1*2+1; 2=2*1+0; so that T(5,3)=10.

Mathematica

T[n_, k_]:= If[k<=0 || k>=n+1, 0, n + T[k, Mod[n, k]]]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] (* G. C. Greubel, Mar 10 2019 *)

Prog

(PARI) {T(n, k) = if(k<=0 || k>= n+1, 0, n + T(k, n % k))};
for(n=1, 12, for(k=1, n, print1(T(n, k), ", "))) \\ G. C. Greubel, Mar 10 2019
(Sage)
def T(n, k):
    if (k==0): return 0
    else: return n + T(n, mod(n, k))
[[T(n, k) for k in (1..n)] for n in (1..12)] # G. C. Greubel, Mar 10 2019

Crossrefs

Cf. A049841 (row sums), A049842 (rows max).

Sequence in context: A039640 A053811 A350167 * A317018 A072039 A204012

Adjacent sequences: A049837 A049838 A049839 * A049841 A049842 A049843

Keyword

nonn,tabl

Author

Clark Kimberling

Extensions

Terms a(70) onward added by G. C. Greubel, Mar 10 2019

Status

approved