A049835 -id:A049835 - cp's OEIS frontend

A049834 Triangular array T given by rows: T(n,k)=sum of quotients when Euclidean algorithm acts on n and k; for k=1,2,...,n; n=1,2,3,...; also number of subtraction steps when computing gcd(n,k) using subtractions rather than divisions.

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

Offset: 1

Clark Kimberling

First quotient=[ n/k ]=Q1; 2nd=[ k/(n-k*Q1) ]; ...

Number of squares in a greedy tiling of an n-by-k rectangle by squares. [David Radcliffe, Nov 14 2012]

			Rows:
1;
2,1;
3,3,1;
4,2,4,1;
5,4,4,5,1;
6,3,2,3,6,1;
7,5,5,5,5,7,1;
...

R. J. Mathar, Table of n, a(n) for n = 1..5050
N. J. A. Sloane, Rows 1 through 100

Cf. A049828.
Row sums give A049835.
This is the lower triangular part of the square array in A072030.

A049834 := proc(n,k)
    local a,b,r,s ;
    a := n ;
    b := k ;
    r := 1;
    s := 0 ;
    while r > 0 do
        q := floor(a/b);
        r := a-b*q ;
        s := s+q ;
        a := b;
        b := r;
    end do:
    s ;
end proc: # R. J. Mathar, May 06 2016
# second Maple program:
T:= (n, k)-> add(i, i=convert(k/n, confrac)):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Jan 31 2023

T[n_, k_] := T[n, k] = Which[n < 1 || k < 1, 0, n == k, 1, n < k, T[k, n], True, 1 + T[k, n - k]];
Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 29 2020 *)

tabl(nn) = {for (n=1, nn, for (k=1, n, a = n; b = k; r = 1; s = 0; while (r, q = a\b; r = a - b*q; s += q; a = b; b = r); print1(s, ", ");); print(););} \\ Michel Marcus, Aug 17 2015

A360264 Sum of mass(k/n) for all k, 1 <= k <= n, that are relatively prime to n.

Original entry on oeis.org

1, 2, 6, 8, 18, 12, 34, 26, 42, 32, 74, 36, 98, 56, 80, 78, 150, 64, 178, 92, 140, 116, 238, 100, 238, 148, 222, 160, 338, 112, 374, 214, 280, 220, 348, 180, 486, 260, 356, 248, 562, 192, 602, 316, 388, 344, 682, 264, 662, 328, 528, 404, 810, 308, 688, 424

Offset: 1

Jeffrey Shallit, Jan 31 2023

nonn

The mass of a rational k/n is the sum of the partial quotients in the continued fraction for k/n. Alternatively, it is the number of steps in the "subtractive algorithm" to compute gcd(k,n).

			For n = 4 the two numbers relatively prime to n are 1 and 3; 1/4 = [0,4] and 3/4 = [0,1,3].  So the sum of all these is a(3) = 8.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Christoph Aistleitner, Bence Borda, and Manuel Hauke, On the distribution of partial quotients of reduced fractions with fixed denominator, ArXiv preprint arXiv:2210.14095 [math.NT], 2022-2023.
Bernhard Liehl, Über die Teilnenner endlicher Kettenbrüche, Arch. Math. (Basel), 40 (1983), 139-147.
A. A. Panov, The mean for a sum of elements in a class of finite continued fractions (in Russian), Mat. Zametki 32 (1982), 593-600, 747; English version, Mathematical Notes of the Academy of Sciences of the USSR 32 (1982), 781-785.
Maurice Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Mag., 54 (1981), 60-63.

Cf. A000010, A049835.

a:= n-> add(`if`(igcd(n, k)=1, add(i, i=convert(k/n, confrac)), 0), k=1..n):
seq(a(n), n=1..60);  # Alois P. Heinz, Jan 31 2023

a[n_] := Total@ Flatten@ (ContinuedFraction[#/n] & /@ Select[Range[n], CoprimeQ[#, n] &]); Array[a, 100] (* Amiram Eldar, Dec 13 2024 *)

Panov (1982) and Liehl (1983) independently proved that a(n) is asymptotically (6/Pi)^2*n*(log n)^2.

A049836 a(n) = Sum_{m=1..n, k=1..m} T(m,k), array T as in A049834.

Original entry on oeis.org

1, 4, 11, 22, 41, 62, 97, 134, 183, 236, 311, 376, 475, 568, 673, 788, 939, 1066, 1245, 1398, 1579, 1772, 2011, 2202, 2459, 2708, 2979, 3240, 3579, 3842, 4217, 4546, 4907, 5280, 5681, 6032, 6519, 6960, 7421, 7848, 8411

Offset: 1

Clark Kimberling

nonn

Partial sums of A049835.

Cf. A049834.

cp's OEIS Frontend

A049834 Triangular array T given by rows: T(n,k)=sum of quotients when Euclidean algorithm acts on n and k; for k=1,2,...,n; n=1,2,3,...; also number of subtraction steps when computing gcd(n,k) using subtractions rather than divisions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A360264 Sum of mass(k/n) for all k, 1 <= k <= n, that are relatively prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A049836 a(n) = Sum_{m=1..n, k=1..m} T(m,k), array T as in A049834.

Views

Author

Keywords

Crossrefs