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

Links

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.

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

Mathematica

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

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