A378568 Lowest weight of rational fraction with denominator n.

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

Offset

1,2

Comments

The weight wt(x) of a rational number x is defined to be the sum of the partial quotients in the continued fraction expansion of x. For example, 5/14 = [0,2,1,4], so wt(5/14) = 7. Here a(n) is the minimum, over all m, 1<=m<n, of wt(m/n).

It is conjectured by Kravitz and Sah that a(n) = O(log n).

Links

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

N. Kravitz and A. Sah, Linear extension numbers of n-element posets, Order 38 (2021), 49-66.

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

Example

For n = 23, we have a(23) = 8 because 5/23 = [0,4,1,1,2] with weight 8, and this is the smallest over all fractions m/23 with 1<=m<23.

Prog

(PARI) a(n)=if(n==1, return(1)); my(r=oo, t); for(m=1, n-1, t=vecsum(contfrac(m/n)); if(t<r, r=t)); r \\ Charles R Greathouse IV, Dec 01 2024

Crossrefs

Sequence in context: A162322 A336155 A196930 * A305437 A111982 A323236

Adjacent sequences: A378565 A378566 A378567 * A378570 A378575 A378576

Keyword

nonn,new

Author

Jeffrey Shallit, Dec 01 2024

Status

approved