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

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

Comments

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

References

B. 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. Mat. Zametki 32 (1982), 593-600, 747.

Links

Table of n, a(n) for n=1..56.

C. Aistleitner, B. Borda, and M. Hauke, On the distribution of partial quotients of reduced fractions with fixed denominator, ArXiv preprint arXiv:2210.14095 [math.NT], October 25 2022.

M. Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Mag., 54 (1981), 60-63.

Formula

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

Example

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.

Maple

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

Crossrefs

Cf. A000010, A049835.

Sequence in context: A182629 A331972 A183212 * A325686 A053355 A233572

Adjacent sequences: A360261 A360262 A360263 * A360265 A360266 A360267

Keyword

nonn

Author

Jeffrey Shallit, Jan 31 2023

Status

approved